Consider the following game.
- Two players each create a passcode using the digits 0-9 four times with repetition allowed.
- The two take turns asking a yes or no question about the opponent's passcode. Players cannot lie.
- If one player asks "Is the password abcd?" on their turn and it is true, they win.
I am trying to find the optimal strategy. My gut feeling is that it is a binary search. Each password corresponds to an integer in the range $[0, 9999]$ so we are guaranteed to find the correct passcode in $\lceil\log_{2} 10000\rceil=14$ questions. Including the final question, the number would be $15$.
However I am unable to prove that this is the best strategy that minimizes the maximum number of questions to be asked. Is this the best strategy. If so, is it possible to prove it?
After $k$ questions, there are only $2^k$ possible sequences of answers. If there are more than $2^k$ possible passwords, then by the pigeonhole principle, there exist two passwords that would give the same sequence of answers, and so it's impossible to know for sure which one if the correct password.
This argument (which doesn't depend at all on the specific identities of the password, only the number $M$ possible passwords) shows that there's no strategy that works in less than $(\log M)/\log 2$ questions. Since the binary search succeeds in $\lceil (\log M)/\log 2\rceil$ questions, it's therefore optimal.