How do I show the optimal strategy for the game 'guess who' is to pick subsets close to half the size of the current set Consider the game guess who. In the game, the chooser chooses a person out of a set of $n$ people. The guesser asks questions such as, 'does the person wear glasses'. By asking such questions the number of people is reduced until the guesser can guess exactly who the person is. The guesser wants to minimize the number of guesses. Intuitively, assuming an equal probability that any given person is chosen, they should ask questions that if true, cut the number of people in half, or as close to half as possible. More generally, I suspect if there is some distribution over the people, the best strategy is to always pick one of the subsets of the current remaining set of people that is as close to having a $50\%$ chance of containing the chosen person.
First, I would like to know if this is correct, and second, I would like to prove this. Currently I am trying to prove this using an argument via entropy however I have been unsuccessful so far.
 A: You can prove by induction that with $n$ questions you can identify an individual out of $2^n$.  You can then show that if one set is larger than $2^{n-1}$ you might need another question, so you have to split that evenly.  If you have a number of people that is not a power of $2$ you have some flexibility in the splits.  For example, if there are $25$ people you can split them anywhere from $9-16$ to $12-13$ and succeed in five questions at worst.
A: The goal of Guess Who is to guess faster than your opponent, and not just to minimize the expected number of guesses. This leads to some situations in which you need to gamble on an unequal split.
For example, suppose Alice and Bob play an $n=4$ game with Alice going first. Alice goes for a 2-2 split, guaranteeing that she eliminates two possibilities. So her next question will definitely be enough to determine Bob's person. If Bob then also goes for a 2-2 split, he'll remain a turn behind Alice, and so has no hope of winning. But if he goes for a 3-1 split, he has a $\frac{1}{4}$ probability of getting ahead of her.
For larger numbers, presumably the second player needs to go for risky splits until one of them pays off, at which point the first player needs to start taking risks.
