Thread: Hilberts Hotel

I came across this and problem and wanted to know how people would go about answering it.

Recall that the Hilbert Hotel doors are numbered 1,2,3,.... Suppose the door to any room can be open or closed. We call these the two states of a door, and we suppose that initially all the doors are closed.

A sequence of robots, R1, R2, R3,..., walk down the corridor, each having a simple program; the first robot, R1 changes the state of every second door and nothing else; R2 changes the state of every third door and does nothing else; in general Rk is to change the state of every (k+1)th door and does nothing else.

a) Provide a succinct and precise reason why each door eventually reaches a final state: it will either be open or closed, depending on the room number.

b) Determine a formula for the number of changes, Change(n), that the door to room n undergoes, in terms of the prime factorization of n.

c) Using your formula for Change(n), what can you say about which doors have a final state that is open, and which have a final state that is closed?

This slightly different but the same idea.