Problem

Source: 2024 CWMO P6

Tags: combinatorics



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.