Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1974 USAMO Problems/Problem 4"

(→‎Solution)
 
(5 intermediate revisions by 3 users not shown)
Line 91: Line 91:
 
Adding the above equations and inequalities, we see that <math>P(TOTAL) > P'(TOTAL)</math>, and thus the father is better off playing the weaker of the two players (ie the mother) first.
 
Adding the above equations and inequalities, we see that <math>P(TOTAL) > P'(TOTAL)</math>, and thus the father is better off playing the weaker of the two players (ie the mother) first.
  
−
==See also==
+
===TL;DR===
 +
Let the probability of the father winning against the son be <math>a</math>, the father winning against the mother be <math>b</math>, and the son winning against the mother be <math>c</math>. Here <math>a<b<\frac{1}{2}</math> and <math>c>\frac{1}{2}</math>.
 +
 
 +
We define three first game cases as above:
 +
 
 +
1. Father vs Mother
 +
 
 +
2. Father vs Son
 +
 
 +
3. Mother vs Son
 +
 
 +
The probability that the father wins (1) (by casework or tree) is <math>P(1)=ab+b^2(1-a)(1-c)+(1-b)abc</math>.
 +
 
 +
The probability that the father wins (2) is <math>P(2)=ab+a^2c(1-b)+ab(1-a)(1-c)</math>.
 +
 
 +
The probability that the father wins (3) is <math>P(3)=ab</math>.
 +
 
 +
Evidently <math>P(1)>P(3)</math>, so all that is left is to prove that <math>P(1)>P(2)</math>.
 +
 
 +
<math>P(1)>P(2)</math>
 +
 
 +
<math>ab+b^2(1-a)(1-c)+(1-b)abc>ab+a^2c(1-b)+ab(1-a)(1-c)</math>
 +
 
 +
<math>b^2(1-a)(1-c)+(1-b)abc>a^2c(1-b)+ab(1-a)(1-c)</math>
 +
 
 +
<math>b(b-a)(1-a)(1-c)>ac(a-b)(1-b)</math>
 +
 
 +
Using the fact that <math>a<b</math>, we easily find that the LHS is positive while the RHS is negative, proving the inequality.
 +
 
 +
~eevee9406
 +
 
 +
{{alternate solutions}}
 +
 
 +
==See Also==
  
 
{{USAMO box|year=1974|num-b=3|num-a=5}}
 
{{USAMO box|year=1974|num-b=3|num-a=5}}
 +
{{MAA Notice}}
  
−
[[Category:Olympiad Inequality Problems]]
+
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 09:29, 6 July 2024

Problem

A father, 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.

Solution

There are three possible strategies for the father:

1) Sit out the first game

2) Play the first game against the weaker of the other two players (the mother). This person is referred to throughout the solution as "the weaker player".

3) Play the first game against the stronger of the other two players (the son). This person is referred to throughout the solution as "the stronger player".


Strategy 1 is dominated by both strategy 2 and strategy 3. If strategy 1 is used and the weaker player wins the first game, it becomes strategy 2, but with the father starting behind 0-1. Likewise, if strategy 1 is used and the stronger player wins the first game, it becomes strategy 3, but with the father again starting behind 0-1.


Thus, the father must play the first game.


By the pigeonhole principle, there may be no more than 4 games; once the 4th game is finished, someone will have won two games. Let $W$ denote a game the father wins, let $L$ denote a game the father loses, and let $x$ denote a game the father does not participate in. Then, with the knowledge that the father plays the first game, the following ways for the father to win two games are possible:

(A) $WW$

(B) $WLxW$

(C) $LxWW$

If the father wins the first game, then he must either win the second game (A), or sit out the third game to win the fourth game (B). If the father loses the first game, then he must sit out the second game and win the third and fourth games (C).

Now we must determine which gives the largest probability of the father winning: playing the first game against the weaker player or the stronger player. We define the following probabilities:

$x$ is the chance of the father defeating the weaker player. $(1-x)$ is the chance of the weaker player defeating the father.

$y$ is the chance of the father defeating the stronger player. $(1-y)$ is the chance of the stronger player defeating the father.

$z$ is the chance of the weaker player defeating the stronger player. $(1-z)$ is the chance of the stronger player defeating the weaker player.

Note that $x > y$, and all of $x, y$ and $z$ are less than $0.5$.

If the father plays the weaker player first, we split the probability of winning the tournament in the three mutually exclusive cases above:

$P(A) = xy$ because the father must defeat the weaker player, then the father must defeat the stronger player.

$P(B) = x(1-y)zx$ because the father must defeat the weaker player, then stronger player must defeat the father. Third, the weaker player must defeat the stronger player (because if the stronger player wins a second game, the tournament is over). Fourth, the father plays the weaker player a second time and must win.

$P(C) = (1-x)(1-z)yx$ because the weaker player must defeat the father, followed by the stronger player defeating the weaker player (because if the weaker player wins two in a row, he wins the tournament). The father must then defeat the stronger player and the weaker player in the third and fourth game, respectively.

From this, the total probability of the father winning by playing the weaker player first is:

$P(TOTAL) = P(A) + P(B) + P(C) = xy + x(1-y)zx + (1-x)(1-z)yx$

Likewise, we compute the probability of the father winning if he plays the stronger player first. We do this by symmetry:

All $x$ will turn into $y$, because whenever the father defeated the weaker player before, he must defeat the stronger player now.

All $y$ will turn into $x$, because whenever the father defeated the stronger player before, he must defeat the weaker player now.

All $z$ will turn into $(1-z)$, because whenever the weaker player defeated the stronger player, now the stronger player must defeat the weaker player.

All $(1-z)$ will turn into $z$, because whenever the stronger player defeated the weaker player, now the weaker player must defeat the stronger player.

Applying these transformations and calling the new probabilities $P'$, we find that:

$P'(TOTAL) = P'(A) + P'(B) + P'(C) = yx + y(1-x)(1-z)y + (1-y)zxy$

We compare these probabilities.

$P(A) = P'(A)$. This makes sense, as the probabilitiy of the father winning the first two games is the same, regardless of the order in which they are played.

$P(B) > P'(C)$: Calculating $P(B) / P'(C)$, we get $x^2(1-y)z / xy(1-y)z$, which simplifies to $x/y$.

Since $x > y$

$x/y > 1$

$P(B) / P'(C) > 1$

so $P(B) > P'(C)$.

$P(C) > P'(B)$: Calculating $P(C) / P'(B)$, we get $(1-x)(1-z)yx / (1-x)(1-z)y^2$, which simpllifies again to $x/y$. Thus, $P(C) > P'(B)$

Adding the above equations and inequalities, we see that $P(TOTAL) > P'(TOTAL)$, and thus the father is better off playing the weaker of the two players (ie the mother) first.

TL;DR

Let the probability of the father winning against the son be $a$, the father winning against the mother be $b$, and the son winning against the mother be $c$. Here $a<b<\frac{1}{2}$ and $c>\frac{1}{2}$.

We define three first game cases as above:

1. Father vs Mother

2. Father vs Son

3. Mother vs Son

The probability that the father wins (1) (by casework or tree) is $P(1)=ab+b^2(1-a)(1-c)+(1-b)abc$.

The probability that the father wins (2) is $P(2)=ab+a^2c(1-b)+ab(1-a)(1-c)$.

The probability that the father wins (3) is $P(3)=ab$.

Evidently $P(1)>P(3)$, so all that is left is to prove that $P(1)>P(2)$.

$P(1)>P(2)$

$ab+b^2(1-a)(1-c)+(1-b)abc>ab+a^2c(1-b)+ab(1-a)(1-c)$

$b^2(1-a)(1-c)+(1-b)abc>a^2c(1-b)+ab(1-a)(1-c)$

$b(b-a)(1-a)(1-c)>ac(a-b)(1-b)$

Using the fact that $a<b$, we easily find that the LHS is positive while the RHS is negative, proving the inequality.

~eevee9406

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1974 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1974_USAMO_Problems/Problem_4&oldid=221761"