Who is "SHE" here?

The Gateway to Computer Science Excellence

+1 vote

A prison houses 100 inmates, one in each of 100 cells, guarded by a total of 100 warders. One evening, all the cells are locked and the keys left in the locks. As the first warder leaves, she turns every key, unlocking all the doors. The second warder turns every second key, re-locking every even numbered cell. The third warder turns every third key and so on. Finally the last warder turns the key in just the last cell. Which doors are left unlocked and why?

0

Door No. 1,4,9,16,25,36,49,64,81,100 left unlocked..

Reason :- These doors have odd number of divisors.. Since initially all doors are unlocked and warder lock the gate if it was unlocked and unlock the gate if it was locked..so, for each gate unlock and lock status will come alternatively..For example :-

Door No.1) Unlocked by warder 1

Door No. 2) Unlocked by warder 1 , Locked by warder 2

Door No. 3) Unlocked by warder 1 , Locked by warder 3

Now, if we analyze it , then if a gate number contains odd number of sequence of locking/unlocking, then it will be ended with unlocked status because it was started with unlocked status. So, after odd number of times it will be in the unlocked state.

Since ,according to question , if we represent door as a number x and warder as a number y then if y divides x then only warder y will lock or unlock it.

Now ,door numbers which give odd numbers of divisors :-

x y

1 = 1

4 = 1,2,4

9= 1,3,9

16 = 1,2,4,8,16...so on...

Since y started with unlocking the doors. So, after odd number of times , it will also be in Unlocked state ..between them it will be in locked and unlocked states alternatively.

So, Conclusion:- if a door no. has odd number of divisors and if it is started with unlocked state then in the end , it will also be unlocked ..

Reason :- These doors have odd number of divisors.. Since initially all doors are unlocked and warder lock the gate if it was unlocked and unlock the gate if it was locked..so, for each gate unlock and lock status will come alternatively..For example :-

Door No.1) Unlocked by warder 1

Door No. 2) Unlocked by warder 1 , Locked by warder 2

Door No. 3) Unlocked by warder 1 , Locked by warder 3

Now, if we analyze it , then if a gate number contains odd number of sequence of locking/unlocking, then it will be ended with unlocked status because it was started with unlocked status. So, after odd number of times it will be in the unlocked state.

Since ,according to question , if we represent door as a number x and warder as a number y then if y divides x then only warder y will lock or unlock it.

Now ,door numbers which give odd numbers of divisors :-

x y

1 = 1

4 = 1,2,4

9= 1,3,9

16 = 1,2,4,8,16...so on...

Since y started with unlocking the doors. So, after odd number of times , it will also be in Unlocked state ..between them it will be in locked and unlocked states alternatively.

So, Conclusion:- if a door no. has odd number of divisors and if it is started with unlocked state then in the end , it will also be unlocked ..

0

*initially all doors are locked..now 1st warder unlocked all these doors..so, now onward if a door no. has odd number of divisors , it means after odd number of times , it will again give odd number ..so it means after odd number of times , doors will be unlocked..

For example :-

Number Divisors

1 = 1

2 = 1,2

3 = 1,3

4 = 1,2,4

5 = 1,5

6 = 1,2,3,6

7 = 1,7

8 = 1,2,4,8

9 = 1,3,9

10 = 1,2,5,10

11 = 1,11

12 = 1,2,3,4,6,12

13 = 1,13

14 = 1,2,7,14

15= 1,3,5,15

16 = 1,2,4,8,16

Now we can analyze it..

For example :-

Number Divisors

1 = 1

2 = 1,2

3 = 1,3

4 = 1,2,4

5 = 1,5

6 = 1,2,3,6

7 = 1,7

8 = 1,2,4,8

9 = 1,3,9

10 = 1,2,5,10

11 = 1,11

12 = 1,2,3,4,6,12

13 = 1,13

14 = 1,2,7,14

15= 1,3,5,15

16 = 1,2,4,8,16

Now we can analyze it..

+2 votes

Best answer

Look if any cell is operated odd number of times then that cell remains open othewise it is closed.

We observe that the mth cell is operated n times where n = no. of divisors of m.

So those cell nos. have odd no. of divisors will be opened at last.

Only perfect square numbers have odd number of divisors (THINK)

So all the perfect square cells will be open

those are 1,4,9,16,25,36,49,64,81,100

We observe that the mth cell is operated n times where n = no. of divisors of m.

So those cell nos. have odd no. of divisors will be opened at last.

Only perfect square numbers have odd number of divisors (THINK)

So all the perfect square cells will be open

those are 1,4,9,16,25,36,49,64,81,100

+1 vote

The initial state of every lock = locked

On every NON-SQUARE numbered door, the number of wanders changing the state will be EVEN. And hence the door will return to locked position.

E.g. Door No.$8$: Warders $1, 2, 4$ and $8$ will act.

Door No.$30$: Warders $1,2,3,5,6,10,15,30$ i.e. a total of $8$ warders will act.

On every SQUARE numbered door, the number of wanders changing the state will be ODD. And hence the door will be in unlocked position.

E.g. Door No.$16$: Warders $1, 2, 4, 8$ and $16$ will act.

Door No.$36$: Warders $1,2,3,4,6,9,12,18,36$ i.e. a total of $9$ warders will act.

So door No. $\color{gold}{1, 4, 9, 16, 25, 36, 49, 64, 84}$ and $\color{gold}{100}$ will be in Open position and rest in Locked position.

Concept used: Perfect squares have odd number of factors and others have even number of factors.

On every NON-SQUARE numbered door, the number of wanders changing the state will be EVEN. And hence the door will return to locked position.

E.g. Door No.$8$: Warders $1, 2, 4$ and $8$ will act.

Door No.$30$: Warders $1,2,3,5,6,10,15,30$ i.e. a total of $8$ warders will act.

On every SQUARE numbered door, the number of wanders changing the state will be ODD. And hence the door will be in unlocked position.

E.g. Door No.$16$: Warders $1, 2, 4, 8$ and $16$ will act.

Door No.$36$: Warders $1,2,3,4,6,9,12,18,36$ i.e. a total of $9$ warders will act.

So door No. $\color{gold}{1, 4, 9, 16, 25, 36, 49, 64, 84}$ and $\color{gold}{100}$ will be in Open position and rest in Locked position.

Concept used: Perfect squares have odd number of factors and others have even number of factors.

52,223 questions

59,818 answers

201,021 comments

118,091 users