Hotel room number problem

Question

There is a building containing N number of hotel rooms. All of these hotel rooms have a unique hotel room number. There is an employee in charge of looking after each hotel room.

One day, the employees are curious to find out the room numbers of all the hotel rooms in the building, so all the employees agree to do an activity.

In this activity, they all start off with a sheet of paper that has an infinite amount of space. They all write the room number of the room they are in charge of at the top of the sheet of paper. Employees can copy the room numbers on another employee’s sheet of paper onto their own sheet of paper. Their end goal is for each employee to have every single room number written on their sheet of paper; this is referred to as finishing. However, no employee knows what the number N is, and they must also follow some criteria. (They must find a method that will allow them to finish while also following this criterion):

A step is when any number of employees copy off another employee’s/employees’ sheet/s of paper. For example, 1 step is where 1 employee copies off another employee’s sheet of paper.

Finishing must happen in a fixed finite number of steps, denoted by S. However, none of the employees know what the number N is and they also have a fixed amount of time to finish, meaning that the chosen method must be able to finish before the maximum number of steps is reached, regardless of how big or small the number N is.

An employee can only do one of two things in a single step; they can let other employees copy off their sheet of paper or they can copy of another employee’s/employees’ sheet/s of paper. They cannot do both in a single step.

Different employees can let other employees copy from them in parallel to each other in a single step, e.g., employee A can copy off employee B’s sheet of paper while employee C is copying off employee D’s sheet of paper and this will only be counted as 1 step.

However, if for example, employee A is copying of employee B’s sheet of paper, and while that is happening, employee B is also copying of employee C’s room numbers, this will be counted as 2 steps and not 1, as employee B cannot copy employee C’s room numbers while also letting employee A copy off them in a single step.

An employee can also copy down an infinite of room numbers in a single step. For example, if employee A has 1000 room numbers written on their sheet of paper and they let employee B copy off them, then this will only be counted as one step.

An employee can also copy down information from M other employees in a single step as well. For example, if M = 100, then employee A can copy down room numbers from a maximum of 100 employees in a single step. The number M, however, must also stay constant regardless of the value of N or S.

Each employee also has the ability to allow an infinite number of other employees copy off their own sheet of paper.

(NOTE: double-ups are where after a certain employee copies from some other employees, they will have two instances of the same room number on their sheet of paper. For example, employee B and C both have the room number "2" written on their sheets of paper and employee A copies from both of them, which will mean employee A will have two instances of the room number "2" written on their sheet of paper (employee A will have a double-up). In this situation, however, double-ups are not a problem and the method used to finish will not necessarily need to prevent double-ups as well.)

The question is, however, is it possible to devise such a method that follows the criteria and description above, or does such a method not exist?

Answer 1

Once you have fixed $M$ and $S$, the task can succeed if and only if $N$ is at most $(M+1)^{S-1}$. In particular there is no $M$ and $S$ that will work for all $N$.

To see that the condition $N\le (M+1)^{S-1}$ is necessary, observe that after step $k$ nobody can possibly have a list with more than $(M+1)^k$ numbers on it. (This can be proved easily by induction on $k$). However, if any copying at all happens in the last step, the employes being copied from in that last step must have reached a full list in the next-to-last step at the latest. So those employees will end with at most $(M+1)^{S-1}$ numbers.

On the other hand, to prove that $N\le(M+1)^{S-1}$ is sufficient, we need to show a concrete strategy that works in that case. Here's one:

1. To begin with, everyone stands up.
2. Do the following step $S-1$ times:
   • All employees who are still standing congregate in groups of size $M+1$.
   • Each group elects a foreperson.
   • Each foreperson copies the lists of the other $M$ persons in his/her group.
   • Everyone who was not a foreperson sits down.
   • (This invariant holds after $k$ steps: There are $(M+1)^{S-1-k}$ people still standing, and every room number appears on one of their lists).
3. After $S-1$ steps there is a single person left standing; they have a complete list. Everyone else copies it off them.

This works as written if there are exactly $(M+1)^{S-1}$ employees. If there are fewer, we need to allow for one of the groups in each step to be smaller than $M+1$ employees. How to arrange that in a hall that is so large that nobody even knows in advance how many people there are in it, I will leave unsaid -- in other words, I assume the the original author of the problem did not intend for that to be a sticking point ...