Olympiad Maths Prep

Track / Stage 5 / 265 of 400 #865 of 2000

Problem 865

AIME late
Algebra Difficulty 5.6 Prove it

Each time, A puts out 1, 2, or 3 stones, and B guesses. If B guesses correctly, the stones A puts out go to B; if B does not guess correctly, B pays A 1 stone. This process is repeated, and the one with more stones at the end wins.
Obviously, this is a zero-sum game problem.
Let the probabilities of A putting out 1, 2, or 3 stones be α1,α2,α3,αi⩾0\alpha_{1}, \alpha_{2}, \alpha_{3}, \alpha_{i} \geqslant 0, then α1+α2+α3=1\alpha_{1}+\alpha_{2}+\alpha_{3}=1;

Let the probabilities of B guessing 1, 2, or 3 stones be β1,β2,β3,βj⩾0\beta_{1}, \beta_{2}, \beta_{3}, \beta_{j} \geqslant 0, then β1+β2+β3=1\beta_{1}+\beta_{2}+\beta_{3}=1.

Then, the number of stones B wins each game, XX, is a random variable, and the probability distribution of XX is shown in Table 1.
Table 1
\begin{tabular}{|c|c|c|c|c|}
\hlineXX & -1 & 1 & 2 & 3 \\
\hline P(X)\mathbf{P}(X) & 1−(α1β1+α2β2+α3β3)1-\left(\alpha_{1} \beta_{1}+\alpha_{2} \beta_{2}+\alpha_{3} \beta_{3}\right) & α1β1\alpha_{1} \beta_{1} & α2β2\alpha_{2} \beta_{2} & α3β3\alpha_{3} \beta_{3} \\
\hline
\end{tabular}

The mathematical expectation of the random variable XX is
E(X)=E(X,α1,α2,α3,β1,β2,β3)=2α1β1+3α2β2+4α3β3−1. \begin{array}{l} \mathrm{E}(X)=\mathrm{E}\left(X, \alpha_{1}, \alpha_{2}, \alpha_{3}, \beta_{1}, \beta_{2}, \beta_{3}\right) \\ =2 \alpha_{1} \beta_{1}+3 \alpha_{2} \beta_{2}+4 \alpha_{3} \beta_{3}-1 . \end{array}

Using the Lagrange multiplier method, we can obtain the unique saddle point of equation (1)
(α1,α2,α3,β1,β2,β3)=(613,413,313,613,413,313). \begin{array}{l} \left(\alpha_{1}, \alpha_{2}, \alpha_{3}, \beta_{1}, \beta_{2}, \beta_{3}\right) \\ =\left(\frac{6}{13}, \frac{4}{13}, \frac{3}{13}, \frac{6}{13}, \frac{4}{13}, \frac{3}{13}\right) . \end{array}

The value at the saddle point is
E(X)=E(X,613,413,313,613,413,313)=−113.  \mathrm{E}(X)=\mathrm{E}\left(X, \frac{6}{13}, \frac{4}{13}, \frac{3}{13}, \frac{6}{13}, \frac{4}{13}, \frac{3}{13}\right)=-\frac{1}{13} \text {. }

From this, we get
(1) A's optimal winning strategy
should be to use the probabilities of putting out stones as
α1=613,α2=413,α3=313. \alpha_{1}=\frac{6}{13}, \alpha_{2}=\frac{4}{13}, \alpha_{3}=\frac{3}{13} .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Prove: When A adopts the above probabilities of showing the stones, no matter what guessing probabilities B adopts (β1、β2、β3,βj⩾0,β1+\left(\beta_{1} 、 \beta_{2} 、 \beta_{3}, \beta_{j} \geqslant 0, \beta_{1}+\right. β2+β3=1)\left.\beta_{2}+\beta_{3}=1\right), there is always E(X)=−113\mathrm{E}(X)=-\frac{1}{13}. However, if A adopts any other probabilities of showing the stones α1′、α2′、α3′,α1′⩾0,α1′\alpha_{1}^{\prime} 、 \alpha_{2}^{\prime} 、 \alpha_{3}^{\prime}, \alpha_{1}^{\prime} \geqslant 0, \alpha_{1}^{\prime} +α2′+α3′=1+\alpha_{2}^{\prime}+\alpha_{3}^{\prime}=1, there must be some αi0′>αi0\alpha_{i_{0}}^{\prime}>\alpha_{i_{0}}. Then, as long as B adopts the guessing probabilities βi0=1,βi0‾=0\beta_{i_{0}}=1, \overline{\beta_{i_{0}}}=0, it can make
E(X)>−113.  \mathrm{E}(X)>-\frac{1}{13} \text {. }
(2) B's best winning strategy

Should adopt the guessing probabilities as
β1=613,β2=413,β3=313. \beta_{1}=\frac{6}{13}, \beta_{2}=\frac{4}{13}, \beta_{3}=\frac{3}{13} .

Prove: When B adopts the above guessing probabilities, no matter what probabilities of showing the stones A adopts (α1、α2、α3,αi⩾0,α4\left(\alpha_{1} 、 \alpha_{2} 、 \alpha_{3}, \alpha_{i} \geqslant 0, \alpha_{4}\right. +α2+α3=1)\left.+\alpha_{2}+\alpha_{3}=1\right), there is always E(X)=−113\mathrm{E}(X)=-\frac{1}{13}. However, if B adopts any other guessing probabilities β1、β2、β3′,βj⩾0\beta_{1} 、 \beta_{2} 、 \beta_{3}^{\prime}, \beta_{j} \geqslant 0, β1+β2+β3=1\beta_{1}+\beta_{2}+\beta_{3}=1, there must be some βj0<βj0\beta_{j_{0}}<\beta_{j_{0}}. Then, as long as A adopts the probabilities of showing the stones αj0=1,αj0‾=0\alpha_{j_{0}}=1, \overline{\alpha_{j_{0}}}=0, it can make
E(X)<−113.  \mathrm{E}(X)<-\frac{1}{13} \text {. }

When both sides of the game adopt their respective best winning strategies, it is easy to know from equation (2) that, at this time, the guessing game is advantageous to A, and

the mathematical expectation of the number of stones A wins each time is 113\frac{1}{13} stones.
Finally, we point out that if the rules of this guessing game: "A shows 1 stone, 2 stones, or 3 stones each time" are changed to "A shows kk stones, 1⩽k⩽n1 \leqslant k \leqslant n", then, when n=1n=1, it is absolutely advantageous to B, at this time B wins 1 stone each time; when n=2n=2, the game is advantageous to B, at this time B's mathematical expectation of the number of stones won each time is 15\frac{1}{5} stones; when n⩾3n \geqslant 3, the game is advantageous to A, at this time A's mathematical expectation of the number of stones won each time is
1−112+13+⋯+1n+1 1-\frac{1}{\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n+1}}

stones, this value increases with the increase of nn.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.