AoPS - Problem

Source: 2024 CWMO P6

Tags: combinatorics

Twoisaprime

07.08.2024 12:34

Alice and Bob now play a magic show. There are $101 $ different hats lie on the table and they form a circle. Firstly, Bob choose a positive integer $n$(Alice doesn’t know it). Then Bob puts a rabbit under one of the hats and Alice doesn’t know which hat contains the rabbit. Each time, she can choose a hat and see whether the rabbit is under the hat. If not, then Bob will move the rabbit from the current hat to the $n$th hat in a clockwise direction. They will repeat these steps until Alice find the rabbit. Prove that Alice can find the rabbit in $201$ steps.

We will provide an explicit construction for this. Label the hats $0,1,2,...,100$ in clockwise order. Then in every move the rabbit moves from hat $k$ to hat $k+n$, where hats are taken mod 101. We first guess hat $0$ 101 times. Suppose the rabbit starts at hat $A$. Then the respective locations of the rabbit for each guess is $A, A+n, A+2n,...,A+100n$. If $n\nmid 101$, then these numbers cover all residues mod $101$, which means that each hat will have been visited by the rabbit on the $101^{th}$ move, so Alice will have guess it by then. Else, we deduce that $101\mid n$. Thus the rabbit will never move, but the rabbit is not on $0$. Therefore, Alice will definitely find the rabbit if she guesses every hat except hat $0$ once. In total, that is $101+(101-1)=201$ times, before she ensures that she can find the rabbit.