In a popular computer game the computer picks an integer from 1 to n at random. The player is given k chances to guess the number. After each guess the computer responds "correct," "too small," or "too big."
(a) Show that if n ≤ 2k - 1, then there is a strategy that guarantees you will correctly guess the number in k tries.
(b) Show that if n ≥ 2k - 1, there is a strategy that assures you of identifying one of 2k - 1 numbers and hence gives a probability of (2k - 1)/n of winning. Why is this an optimal strategy? Illustrate your result in terms of the case n = 9 and k = 3.