5. [8] At night, 100 tourists arrived at a hotel. They know that the hotel has single rooms 1, 2, ..., n, of which k are under repair (but it is unknown which ones), and the rest are free. The tourists can agree in advance on their actions, after which they go to check in one by one: each checks the rooms in any order, finds the first free room not under repair, and stays there for the night. However, the tourists do not want to disturb each other: it is not allowed to check a room where someone has already checked in. For each k, indicate the smallest n for which the tourists can guarantee they will be able to check in without disturbing each other.

Fedor Ivlev
Answer: $n=100(m+1)$ for $k=2 m$ and $n=100(m+1)+1$ for $k=2 m+1$.

Solution. Let $k=2 m$ or $k=2 m+1$.

Algorithm. Mentally divide the room numbers into 100 segments, each containing $m+1$ numbers, and in the case of an odd $k$, declare the remaining number as a spare. Let the $i$-th tourist first check all the rooms in the $i$-th segment, moving from left to right, then go to the spare room (if it exists), and then check the rooms in the $(i+1)$-th segment, but from right to left (if $i=100$, check the 1st segment). No two tourists will end up in the same room, as the total number of rooms in their two segments (including the spare room, if it exists) is $k+2$.

Estimation. For each of the 100 tourists to be able to guarantee a room not under repair, they must initially have a list of $k+1$ different rooms to check. We can assume that these lists do not change as other tourists check in (since we do not learn any information about them).

Consider the first $m+1$ rooms in each tourist's list. All these $100(m+1)$ numbers are distinct; otherwise, two tourists with the same number could both end up in that room (if their previous rooms, which total no more than $m+m=2m$, are all under repair). Therefore, $n \geqslant 100(m+1)$.

For even $k$, this estimate is sufficient. In the case of odd $k$, if some tourist, say Petya, has a $(m+2)$-th room that coincides with one of the $100(m+1)$ "first" rooms, say Vasya's, then when Petya's first $m+1$ rooms are under repair and Vasya's rooms up to the one coinciding with Petya's (no more than $m$) are under repair, they will end up in the same room. Therefore, all $(m+2)$-th rooms must be different from the $100(m+1)$ first rooms (although they can coincide with each other), so $n \geqslant 100(m+1)+1$.

Remark. For an even number of tourists (which we have 100), the algorithm can be described differently.

For even $k$, we can mentally represent the hotel plan as 50 corridors, each with doors to $k+2$ rooms along one wall. We assign one corridor to each pair of tourists, who move from opposite ends, checking all the rooms they encounter. In total, this pair can find no more than $k$ rooms under repair, so two free rooms will remain for them.

For odd $k$, we can represent the corridors of the hotel as the major diagonals of a regular 100-gon: each diagonal has $k+2$ rooms, with one room common to all corridors (the image shows a similar construction for 6 tourists and $k=5$). Each pair of tourists moves from opposite ends along their own corridor. Note that if a tourist reaches the central room, they have found $\frac{k+1}{2}$ rooms under repair, so no other tourist will reach the central room.

![](https://cdn.mathpix.com/cropped/2024_05_06_77a17bb6318cfbeb3700g-4.jpg?height=274&width=312&top_left_y=427&top_left_x=1644)