Question 95
The Brazilian IMO leader chooses two natural numbers $n$ and $k$ with $n\gt k$ and tells them to his deputy and to a contestant. Then the leader whispers a binary sequence of length $n$ into the deputy's ear. The deputy writes down all binary sequences of length $n$ that differ from the leader's sequence in exactly $k$ positions. (Example for $n=3$ and $k=1$: if the leader chooses 101, the deputy writes down 001, 100, 111.) The contestant looks at the sequences the deputy has written down. Now the contestant tries to find out the leader's original sequence.
What is the minimum number of guesses he needs (depending on $n$ and $k$) until he has certainly guessed correctly once?
What is the minimum number of guesses he needs (depending on $n$ and $k$) until he has certainly guessed correctly once?