[ Algorithm Theory (miscellaneous).] Evaluation + example $\quad]$

Authors: Blinkov A.D., Blinkov Y.A., Gorska E.S.

A casino offers a game with the following rules. The player bets any whole number of dollars (but no more than they currently have) on either heads or tails. Then a coin is flipped. If the player guesses correctly how it will land, they get back their bet and an equal amount of money in addition. If they guess incorrectly, the casino takes their bet. If the player is unlucky four times in a row, the casino awards them a consolation win in the next game regardless of how the coin lands. Joe came to the casino with 100 dollars. He agreed to make exactly five bets and never to bet more than 17 dollars. What is the largest amount of money he can guarantee to take away from the casino after such a game?
The main observation in this problem is this: as soon as the player guesses correctly how the coin will land once, they can guess incorrectly in all remaining games. Therefore, all bets after a win should be $1.

1. The first time, the player has to bet at least $3, because they could win this game and lose the next four.
2. If they lost the first game, then in the second game, they would have to bet at least $5: because they might win only this round and lose at least $3 from the previous game and at least $3 from the next three.
3. If they lost the second game as well, then their bet on the third game should be at least $9: if they win, they need to make up for at least $10 in losses (3 for the first game, 5 for the second, and 1 each for the fourth and fifth).
4. If they lost the third game as well, then on the fourth game, they would have to bet at least $17: the win should make up for at least $3 + 5 + 9 + 1 = 18$ dollars in losses.
5. If they lost the fourth game as well, then they have already lost at least $3 + 5 + 9 + 17 = 34$ dollars, and even the maximum bet of $17$ dollars cannot compensate for the loss.

Now let's prove that the player can bet in such a way that they will lose no more than $2. Similarly to the above reasoning, we understand that as long as the player is losing, they should bet $2, then $3, $5, $9, and $17, and as soon as they win, they should bet $1 in all subsequent rounds. It is easy to check that in every situation, the player will lose no more than $2.

Comment. Note that if the player is allowed to bet no more than 5 times, they can "end up in the plus." For this, they only need to bet $1, $2, $4, $8, and $16 and leave after they win: then they will definitely win $1. The proof that in this case, they cannot win more is similar to the proof in the solution.

## Answer

98.

Submit a comment