Suppose there are infinitely many coaches with infinitely many members in each coach. They stay at the hotel for infinitely many days. I know that guests can be accommodated using various methods like the prime powers method, but there's a slight variation in the question which is that the guests have to change their room every day such that one guest can't occupy the same room again (i.e., they have to occupy unique rooms every day). How can we achieve that?
I tried solving the problem using the following method:
-
I allotted rooms using the prime powers method.
-
The next day, guests move from their current room $x$ to the new room $x+c$.
I'm struggling after this step. Can someone please help me out?
Best Answer
A far simpler approach than prime powers is as follows. Number the rooms starting from $0$. Each day,
This creates an infinite cycle linking every room, on which all guests move: $$\dots\to5\to3\to1\to0\to2\to4\to6\cdots$$ So not only is it possible to have all guests occupy different rooms on infinitely many days, it is possible to achieve full utilisation while doing so for all eternity.
If all rooms can only ever be occupied by at most one guest, the following construction (also simpler than prime powers) still ensures that every room is eventually used. Arrange the rooms in an array like this, and this time start from $1$: $$\begin{array} 01&2&4&7&11&\dots\\ 3&5&8&12&17&\dots\\ 6&9&13&18&24&\dots\\ 10&14&19&25&32&\dots\\ 15&20&26&33&41&\dots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}$$ On the first day, the guests stay in triangular-numbered rooms, i.e. the first column of the above array. Each subsequent day, all guests move to the room that is to their immediate right in the array, e.g. $6$ moves to $9$, then to $13$ and $18$, etc.
Both solutions here are based on canonical bijections to $\mathbb N$, from $\mathbb Z$ and $\mathbb N^2$ respectively.