Timothy Qian of Rockville, Maryland, was another winner of this year’s Science Talent Search. Like Wenjun, Timothy’s work related to quantum computing — he analyzed the bounds on how much information you can glean from a quantum system. And it just so happens that his favorite puzzle, developed with fellow student Gabriel Wu, is all about leveraging the information in a game to maximize your winnings:
You will be asked four seemingly arbitrary true-or-false questions by the Sphinx on a topic about which you know absolutely nothing. Before the first question is asked, you have exactly $\$1$. For each question, you can bet any non-negative amount of money that you will answer correctly. That is, you can bet any real number (including fractions of pennies) between zero and the current amount of money you have. After each of your answers, the Sphinx reveals the correct answer. If you are right, you gain the amount of money you bet; if you are wrong, you lose the money you bet.
However, there’s a catch. (Isn’t there always, with the Sphinx?) The answer will never be the same for three questions in a row.
With this information in hand, what is the maximum amount of money you can be sure that you’ll win, no matter what the answers wind up being?
Extra credit: This riddle can be generalized so that the Sphinx asks $N$ questions, such that the answer is never the same for $Q$ questions in a row. What are your maximum guaranteed winnings in terms of $N$ and $Q$?
The answers will alternate. You can be sure of every answer except the first one. You should therefore bet all for each question after the first.
Your winnings for each question are thus
| Number of Question | $1$ | $2$ | $3$ | $4$ | ... | $N$ |
|---|---|---|---|---|---|---|
| Your Winnings | $\$0$ | $\$1$ | $\$2$ | $\$4$ | ... | $ \$ 2^{ \left( N-2 \right) }$ |
$$= \sum_{n=0}^{N-2} 2^{n}$$
$$= 2^{N-1}-1$$
In order to maximize your winnings, only bet after two answers being the same. If no consecutive answers are the same, you shouldn't bet, hence your winnings would end up $0$.
In order for you to achieve that maximum account, the sphinx would have to alternate two trues and two falses. However, you are not sure of that, so you only bet as mentioned in the previous statement.
Your winnings for each question are thus
| Number of Question | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | ... | $N$ (odd) |
|---|---|---|---|---|---|---|---|---|---|---|
| Your Winnings | $\$0$ | $\$0$ | $\$1$ | $\$0$ | $\$2$ | $\$0$ | $\$4$ | $\$0$ | ... | $\$ 2^{ \left( \frac{N-3}{2} \right) }$ |
There are can be at most one known group of two consecutive questions with the same answer in four questions. Your maximum guaranteed winnings are therefore
$$\$1$$In order to maximize your winnings, only bet after $Q-1$ answers being the same. If $Q-1$ consecutive answers are never the same, you shouldn't bet, hence your winnings would end up $0$.
In order for you to achieve that maximum account, the sphinx would have to alternate $Q-1$ trues and $Q-1$ falses. However, you are not sure of that, so you only bet as mentioned in the previous statement.
Every $Q-1$ questions can be treated as one, so the maximum total winnings are thus
$$ 2^{\left\lceil \frac{N}{Q-1} \right\rceil -1}-1 $$