The guess-a-number game starts with one player (the chooser) picking a number between 1 and 100 (inclusive) and secretly writing it down. The other player (the guesser) attempts to guess the number. After each guess, the chooser responds with "correct" (the guesser guessed the number and the game is over), "higher" (the actual number is higher than the guess), or "lower" (the actual number is lower than the guess).
a. Explain why the guesser can receive slightly more than one bit of information for each response.
b. Assuming the chooser picks the number randomly (that is, all values between 1 and 100 are equally likely), what are the best first guesses? Explain why these guesses are better than any other guess. (Hint: there are two equally good first guesses.)
c. What is the maximum number of guesses the second player should need to always find the number?
d. What is the average number of guesses needed (assuming the chooser picks the number randomly as before)?
e. Suppose instead of picking randomly, the chooser picks the number with the goal of maximizing the number of guesses the second player will need.
What number should she pick?
f. How should the guesser adjust her strategy if she knows the chooser is picking adversarial?
g. What are the best strategies for both players in the adversarial guess a number game where chooser's goal is to pick a starting number that maximizes the number of guesses the guesser needs, and the guesser's goal is to guess the number using as few guesses as possible.