At an international combinatorial conference, a hundred mathematicians are accommodated in a hotel where the rooms are numbered from one to a hundred. The receptionist plans to assign the mathematicians to the rooms corresponding to their arrival order. However, the first arriving guest is forgotten to be given the correct instruction, so they randomly choose one of the rooms. In the end, the receptionist instructs the rest to sequentially occupy the room corresponding to their arrival order; if that room is already occupied, they should randomly choose one of the available rooms. In how many ways can the guests be accommodated in the rooms?
I. solution. We claim that $k$ mathematicians can check into the rooms in $2^{k-1}$ ways. We prove this by complete induction.

$k=1$: One person can check into one room in only $1=2^{0}=2^{1-1}$ way.

$k=2$: The first person checks into one of the two rooms, and the second person has no choice, so they can check in in $2=2^{1}=2^{2-1}$ ways.

Now suppose that for some $k$ (where $k \geq 2$), the statement is true for all positive integers up to $k$. We will show that it is also true for $k+1$, i.e., $k+1$ mathematicians can check into the rooms in $2^{k}$ ways.

If the first person checks into their own room (the first numbered one), then everyone else will check into their designated room, so this is one way of checking in.

If the first person checks into the $n$-th room ($2 \leq n \leq k+1$), then everyone up to the $(n-1)$-th person can occupy their designated room. Consider the remaining mathematicians, whose number is $(k+1)-(n-1)=k-n+2$. The $n$-th person has had their room taken by the first person, but the others' rooms are still free. Notice that these $k-n+2$ mathematicians are in the same situation as if they were the only ones in the hotel and no one had arrived before them. Each has their designated room: it can be interpreted as if the $n$-th person's room were the 1st room, they arrived first, and the receptionist forgot to give them the instructions. Therefore, if the first person checks into the $n$-th room ($2 \leq n \leq k+1$), the others can occupy the rooms in $2^{(k-n+2)-1}$ ways (by the induction hypothesis).

Since $n$ can be any value between 2 and $k+1$, summing these up gives the number of ways $k+1$ mathematicians can choose rooms:

$$
\begin{gathered}
1+\sum_{n=2}^{k+1} 2^{(k-n+2)-1}=1+\sum_{n=2}^{k+1} 2^{k-n+1}= \\
=1+\left(2^{k-1}+2^{k-2}+\ldots+2^{1}+2^{0}\right)=1+\left(2^{k}-1\right)=2^{k}
\end{gathered}
$$

Thus, the guests can check into the rooms in $2^{99}$ ways.

Weisz Máté (Szegedi Radnóti Miklós Kís. Gimn