A father, a mother and son hold a family tournament, playing a two person board game with no ties. The tournament rules are: (i) The weakest player chooses the first two contestants. (ii) The winner of any game plays the next game against the person left out. (iii) The first person to win two games wins the tournament. The father is the weakest player, the son the strongest, and it is assumed that any player's probability of winning an individual game from another player does not change during the tournament. Prove that the father's optimal strategy for winning the tournament is to play the first game with his wife.
Problem
Source: 1974 USAMO Problem 4
Tags: probability
12.07.2013 17:00
Let $F,M$ and $S$ denote father , mother and son respectively . Define , $\overleftarrow{AB}$ means , $A$ won and $B$ loses . And $P(\overleftarrow{AB}) = \overline{AB}$ Now note that if $F$ and $M$ plays first then , $F$ will win the tournament , if anyone of the three sequence follow . \[\overleftarrow{FM} , \overleftarrow{FS}\] \[\overleftarrow{FM} , \overleftarrow{SF} , \overleftarrow{MS} , \overleftarrow{FM}\] \[ \overleftarrow{MF} , \overleftarrow{SM} , \overleftarrow{FS} , \overleftarrow{FM}\] If , $F$ and $S$ plays the first game , $F$ will tournament then ( then any of the above three sequence follow ( with $M$ and $S$ reversed ) . If $M$ and $S$ play's the first game , $F$ will tournament if , \[\overleftarrow{MS} , \overleftarrow{FM} , \overleftarrow{FS} \] \[\overleftarrow{SM} , \overleftarrow{FS} , \overleftarrow{FM} \] Now , if the first case happen's then , \[ P_{\text{ F winning the tournament if F and M play's first}}= \overline{FM}\cdot\overline{FS}+\overline{FM}\cdot\overline{SF}\cdot\overline{MS}\cdot\overline{FM}+\overline{MF}\cdot\overline{SM}\cdot\overline{FS}\cdot\overline{FM}\] If , second case happen , then \[ P_{\text{ F winning the tournament if F and S play's first}} = \overline{FS}\cdot\overline{FM}+\overline{FS}\cdot\overline{MF}\cdot\overline{SM}\cdot\overline{FS}+\overline{SF}\cdot\overline{MS}\cdot\overline{FM}\cdot\overline{FS}\] If third case happen then , \[P_{\text{ F winning the tournament if M and S play's first}} = \overline{SM}\cdot\overline{FS}\cdot\overline{FM}+\overline{MS}\cdot\overline{FM}\cdot\overline{FS} = \overline{FS}\cdot\overline{FM}\] . Note that the third case probablity is very less . Now , $P_{\text{ F winning the tournament if F and M play's first}} - P_{\text{ F winning the tournament if F and S play's first}} = ( \overline{FM} - \overline{FS}) ( \text{positive expression}) $ since $S$ is strong player , tactically , $ \overline{FM} - \overline{FS} > 0 $ . So we are done $\Box$
12.04.2023 01:44
Let $p$ be the probability that the father beats the mother, let $q$ be the probability that the father beats the son, and let $r$ be the probability that the mother beats the son. By the "strength" conditions, $0<p,q,r<1/2.$ and $q<p,r$. Note that if the father plays the mother first, the probability of winning is $$p(q+(1-q)rp)+(1-p)(1-r)qp=2pq+rp-2pqr-p^2q+p^2qr.$$Similarly, if he plays the son first, the probability of winning is $$q(p+(1-p)(1-r)q)+(1-q)pqr=pq+q^2-pq^2-rq^2+pqr.$$ Therefore, it suffices to prove the inequality $$2pq+rp-2pqr-p^2q+p^2qr\geq pq+q^2-pq^2-rq^2+pqr$$for positive reals $0<p,q,r<1/2$ with $q<p,r.$ (the case where the father lets the other two play is $pq$, which is clearly smaller than both of these). This can be rearranged to $$pq+rp+p^2qr+pq^2+rq^2\geq q^2+3pqr+p^2q.$$We will instead prove the stronger result $$pq+rp+pq^2+rq^2\geq q^2+3pqr+p^2q$$(the $p^2qr$ term was removed from the left). Note that this can be expressed as $$r(p+q^2-3pq)+pq+pq^2\geq q^2+p^2q.$$Since this is linear in $r$, it suffices to prove the inequality for the two "extreme" values, which we will use $r=0$ and $r=1/2$ as the extreme values. For $r=0$, we want to prove that $$pq+pq^2\geq q^2+p^2q.$$Reducing by $q$, this becomes $$p+pq\geq q+p^2,$$which rearranges to $$p(1-p)\geq q(1-p),$$which is clearly true as we know $q<p$. For $r=1/2$ we want to prove that $$(1/2)(p+q^2-3pq)+pq+pq^2\geq q^2+p^2q$$$$p+2pq^2\geq q^2+2p^2q+pq.$$Note that since $pq\geq q^2$, it suffices to show that $$p+2pq^2\geq pq+2p^2q+pq.$$Reducing by $p$, this is $$1+2q^2\geq 2q+2pq.$$However, note that $1>2p$, so it suffices to show that $$p+q^2\geq q+pq.$$This rearranges to $$p(1-q)\geq q(1-q),$$which is clearly true, so we are finally done.
13.04.2023 08:48
This is actually a really nice problem, it looks intimidating but really becomes algebraic inequalities bash! If we set probability that father beats mother, father beats son, and mother beats son as a, b, and c, with 0<a,b,c,<1/2, and b<a and c, then we can express everything in terms of variables, and it is simple bash from there. @above nice, I did the same thing