Number Theory

1 vote
203 views
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?

recategorized
0
Who is "SHE" here?
0
warder
0
Only door 1 and 4?
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 ..
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..
0
Yes, the square number of cells are left unlocked
0
1,4,9,16,25,36,49,64,81,100 is the answer the reason is given below
0

Kushagra Chatterjee what do you think about door $99$?

1
99 divisors are 1,3,9,11,33,99

1st time unlock

2nd time lock

3rd time unlock

..............

last time lock
0
$Mk Utkarsh$  99 will be closed because all the numbers except the perfect square nos. have even no. of divisors

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

selected
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.

edited
0
Why square nos. have even number of factors

Related questions

1
80 views
Why does a perfect square number have odd number of factors?
Find the remainder of $\frac{9^{1}+9^{2}+...+9^{n}}{6}$ where $n$ is multiple of 11. I am getting $0$ or $3$. But given answer is 3. Can anyone check?
If $N = 1!+2!+3!+...+10!$. What is the last digit of $N^{N}$?
If $a$ and $b$ are integers and $a-b$ is even, which of the following must always be even? $ab$ $a^{2}+b^{2}+1$ $a^{2}+b+1$ $ab-b$