Question 6
100 tourists arrive at a hotel with single rooms numbered $1,2,\ldots,n$. Exactly $k$ rooms, with unknown numbers, are under repair; the others are vacant. Each tourist checks rooms in a chosen order, possibly different for different tourists, and takes the first room not under repair. They cannot see occupancy before checking a room and must never check a room already occupied by another tourist. They coordinate a strategy beforehand. For each $k$, find the smallest $n$ guaranteeing success. (10 points)
Neutral editorial illustration.
Neutral editorial illustration.