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 <= 2^k−1, then there is a strategy that guarantees you will correctly guess the number in k tries. (b) Show that if n >= 2^k−1, there is a strategy that assures you of identifying one of 2^k− 1 numbers and hence gives a probability of (2^k− 1)/n of winning. Why is this an optimal strategy?
(Book - Introduction to Probability 2nd ed., Grinstead and snell question 6.1 # 28 )