A hundred tourists arrive to a hotel at night. They know that in the hotel there are single rooms numbered as $1, 2, \ldots , n$, and among them $k{}$ (the tourists do not know which) are under repair, the other rooms are free. The tourists, one after another, check the rooms in any order (maybe different for different tourists), and the first room not under repair is taken by the tourist. The tourists don’t know whether a room is occupied until they check it. However it is forbidden to check an occupied room, and the tourists may coordinate their strategy beforehand to avoid this situation. For each $k{}$ find the smallest $n{}$ for which the tourists may select their rooms for sure. Fyodor Ivlev
Problem
Source: 42nd International Tournament of Towns, Junior A-Level P6 & Senior A-Level P5, Spring 2021
Tags: combinatorics, Process, Tournament of Towns
sn6dh
18.02.2023 18:40
Let $f(i, j):=$ the $j$-th room that the $i$-th tourist will check in the strategy. In the following for convenience, suppose that if a tourist check an occupied room, he will explode immediately. Lemma: if $f(i_1, j_1)=f(i_2, j_2)$ for some $i_1<i_2$, then "$j_1+j_2\geq k+3\iff$ when $i_2$ is checking the $j_2$-th room, $i_2$ won't explode in this strategy for sure." Proof: $(\Rightarrow)$ If $f(i_1, j_1)$ is under repair, then the lemma holds. If $i_2$ had checked another room that is occupied by $i_1$, then he would had exploded. Otherwise, in $f(i_1, 1), f(i_1, 2), \dots, f(i_1, j_1-1), f(i_2, 1), f(i_2, 2), \dots, f(i_2, j_2-1)$, there are at least $k+1$ rooms, and therefore exists at least a room that is not under repair. $\Rightarrow$ either $f(i_1, j_1)$ won't be occupied by $i_1$, or $i_2$ won't check this room. $(\Leftarrow)$ If $j_1+j_2\leq k+2$, and the $k$ rooms $f(i_1, 1), f(i_1, 2), \dots, f(i_1, j_1-1), f(i_2, 1), f(i_2, 2), \dots, f(i_2, j_2-1)$ are under repair, then $i_2$ will explode in this strategy when checking the $j_2$-th room. By the lemma: a strategy will success $\iff\forall i_1\neq i_2$ and $j_1, j_2$, if $f(i_1, j_1)=f(i_2, j_2)$, then $j_1+j_2\geq k+3$. If $k=2l-1$ is odd, then $\forall i_1\neq i_2,\ (j_1, j_2\leq l$ or $j_1=l+1, j_2\leq l),\ f(i_1, j_1)\neq f(i_2, j_2)$. $\Rightarrow n\geq100l+1$. If $k=2l$ is even, then $\forall i_1\neq i_2,\ j_1, j_2\leq l+1,\ f(i_1, j_1)\neq f(i_2, j_2)$. $\Rightarrow n\geq100(l+1)$. Construction: If $k=2l-1$ is odd, let $$f(i, j)=\begin{cases} l(i-1)+j\text{, if }j\leq l\\ 100l+1\text{, if }j=l+1\\ l(100-i)+2l+2-j\text{, if }j\geq l+2 \end{cases}$$If $k=2l$ is even, let $$f(i, j)=\begin{cases} (l+1)(i-1)+j\text{, if }j\leq l+1\\ l(100-i)+2l+3-j\text{, if }j\geq l+2 \end{cases}$$ $\therefore$ the answer is: $2\nmid k: 50k+51$ $2|k: 50k+100$