Hilbert's Prison

Number Theory Level 2

Consider a prison with infinite rooms numbered as 1, 2, 3,......

Initially all the prison doors are locked.

An infinite number of rioters break in and disturb the rooms in the following way.

First one stops at all rooms and opens them all.

Second rioter stops at rooms numbered 2, 4, 6,...... and locks open rooms, and leaving the other rooms as they were.

The third rioter stops at rooms numbered 3, 6, 9,.... and again opens a locked room and locks an open room, leaving others undisturbed.

And this process continues.

After all the infinite rioters have left, which rooms would be open?

The prime numbered rooms. The squared numbered rooms. The even numbered rooms. The odd numbered rooms.

3 solutions

Samuel Youhanna
Jun 3, 2014

because only the square numbers are reached odd number of times!!! for example: 16: is reached by 1,2,4,8,16 while 8 is reached by 1,2,4,8

Then what about room no. 1,5,7,11,etc prime nos. Cz they are also open?

Ambar Chandra - 7 years ago

1 is not a prime no. and it is a squared number - it'll be open prime numbers like 2,3,5,7,11, etc have exactly 2 factors; and thus will be toggled only twice (namely by person 1 and person # = number) so originally being locked, they'll remain locked, not open.

Anonyo Palit - 6 years, 11 months ago

i dont get it

toben maurer - 7 years ago

i thought 4 is a squared number?

Jonathan Moey - 6 years, 11 months ago

The question is a bit ambiguous. I first tought that after the third rioter the fourth would have been as the first, the fifth as the second, the sixth as the third, then the first another time and so on, and that way it seems that only primes, but not 2 and 3, plus the 1 remains always open. A second possibility is that after the third rioter the fourth changes 4,8,12... the fifth 5,10,15... and so on, and in that case only squares remains open in the end.

MDA DS - 6 years, 10 months ago

Annabelle Pan
Jun 9, 2014

The rioters can be thought of as multiples. The only doors open will have an odd number of multiples. Say you write out the multiples in a row in increasing order, for 16 that would be 1,2,4,8,16. For 24, that would be 1,2,3,4,6,8,12,24. Notice how multiplying a number on that list by its 'reflection' on the list gives the number it's a multiple of, like for 24, 1x24, 2x12, 3x8. What's special about squared numbers is that at the very middle of the list, there's just one number (for 16, that's 4--the middle number will be the square root) instead of a pair (4x6 for 24). Because of that, perfect squares will have an odd number of multiples, an odd number of rioters will touch them, and they will be open.

Rahil Shah
Jun 6, 2014

1^2=1 2^2=1+3 3^2=1+3+5 4^2=1+3+5+7 ...and so on.....so only square number doors are open..

Then what about room no. 1,5,7,11,etc prime nos. Cz they are also open?

mohmaed rashad - 6 years, 12 months ago

5 starts open.

The sequence (5, 10, 15, 20, ...) closes it.

Nothing else changes it.

2 and 3 are primes you missed. It is evident that not ALL primes will be open.

Bernardo Sulzbach - 6 years, 11 months ago

but 1 remains opened

devansh agarwal - 7 years ago

1is square of itself

Ativ Joshi - 7 years ago

Hilbert's Prison

3 solutions

0 pending reports