Track / Stage 7 / 22 of 300 #1422 of 1964

Problem 1422

National Olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.0 Prove it Olimpiadi di Matematica · Italy

Martino thinks he has discovered a method to win at roulette, or at least not to lose too much money. He always bets on red. He starts by betting 1 euro; every time he loses he doubles the previous bet, while every time he wins he bets 1 euro on the next play. One day he has 31 euros with him and goes to play, deciding that he will leave as soon as either he has lost 5 times in a row, or he has won 5 times in a row, or he has run out of money before one of these two possibilities has occurred.

a. What will be the minimum number of plays he must make in order to finish playing with 31 euros, if he leaves after 5 losses?

b. What will be the minimum number of plays he must make in order to finish playing with 31 euros, if he leaves after 5 wins?

c. If he leaves after 5 wins, what will be his minimum final capital?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

Let us begin by proving a preliminary result: every time he wins after a sequence of losses (provided he does not stop before), Martino finds himself with 1 euro more than he had before he started losing, that is, after the previous win. This is because if he has $n$ euros in hand and plays winning on the $k$ -th attempt $(k \geq 1)$ he will have in hand
$n-\sum_{i=1}^{k-1} 2^{i}+2^{k}=n-\left(2^{k}-1\right)+2^{k}=n+1$
coins.

In other words, if at the beginning of a sequence of losses (that is, at the beginning of the game or after a win) he has $k$ euros and wins on the first try he will have $k+1$ euros; but even if he wins after losing once he will have $k-1+2=k+1$ euros, and so on (for example losing 3 times, he will have lost $1+2+4=7$ euros, but on the next bet he stakes 8 and if he wins he will again have $k-1-2-4+8=k+1$ euros). After a win, therefore, Martino will always have exactly one euro more than after the previous win, as we wanted to show.

Having made this observation we can tackle the three parts of the problem.

a.
If Martino finishes playing having lost 5 times in a row, it means he has lost 31 euros and therefore before losing the first of these 5 times he must have had 62 euros. This, thanks to the previous observation, implies that, before the last series of 5 losses, Martino has won at least 31 times and has never won nor lost more than four consecutive plays (otherwise he would have stopped playing earlier). So he has lost at least $\left[\frac{31}{4}\right]=7$ times and the number of plays is therefore at least $31+7+5=43$ .

Let us show how it is actually possible to play 43 times and come out with 31 euros after 5 losses: writing V and S for win and loss, with the sequence

VVVVS VVVVS VVVVS VVVVS VVVVS VVVVS VVVVS VVVSS SSS

exactly the required situation is realized (a final capital of 31 euros). Martino's capital indeed has this behavior:

b.
The described situation cannot occur. Indeed the reasoning we have seen applies in particular to the first play and allows us to deduce that after a win Martino always has at least 32 euros, so it is not possible for him to leave with 5 wins and only 31 euros in hand.

c.
Therefore, taking into account the initial observation, if Martino leaves with 5 wins he can never have less than 36 euros; on the other hand, if he wins the first 5 bets he leaves with exactly 36 euros.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty, ordering) added by this project.