[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

In a popular computer game the computer picks an integer

from 1 to [math]n[/math] at random. The player is given [math]k[/math] chances to guess the number. After each guess the computer responds “correct,” “too small,” or “too big.”

• Show that if [math]n \leq 2^k - 1[/math], then there is a strategy that guarantees you will correctly guess the number in [math]k[/math] tries.
• Show that if [math]n \geq 2^k - 1[/math], there is a strategy that assures you of identifying one of [math]2^k - 1[/math] numbers and hence gives a probability of [math](2^k - 1)/n[/math] of winning. Why is this an optimal strategy? Illustrate your result in terms of the case [math]n = 9[/math] and [math]k = 3[/math].