20
$\begingroup$

Let $k < n$, $k$ even, $n$ odd. Mary is to play $n$ chess games against her parents, alternating between her father and mother. To receive her allowance she must win $k$ games in a row. Given the choice, should she start against the stronger or weaker parent?

The puzzle source is apparently Peter Winkler.

$\endgroup$
0

8 Answers 8

15
$\begingroup$

Mary should play the

stronger

parent first.

As a simple example, consider a case of k=2, n=3, where Mary wins 100% of games against one parent and 50% against the other. If she plays the weaker parent first, she definitely wins the first game, and has a 50% chance of winning the second, for an overall 50% chance of success. Her entire fortune rests on the outcome of the second game only.

If instead she plays the stronger parent first and wins, she has succeeded since she'll definitely win the second game. But if she loses the first game against the stronger parent, she gets another chance to beat them in the third game - she has an overall 75% chance of succeeding (50% chance in the first game, and another 50% of that in the third game).

No matter the choice of n, k, or probabilities, Mary must win a minimum of $k/2$ games against each parent. She must do this within the $(n+1)/2$ games against the first parent and $(n-1)/2$ against the second parent. The win-rate against the first parent must be at least $k/(n+1)$, while the win-rate against the second parent must be at least $k/(n-1)$, which is larger. Mary should prefer to not require the higher win-rate against the stronger opponent, so she should play the stronger opponent first.

$\endgroup$
0
13
$\begingroup$

Mary should play her first game against

the stronger parent.

To prove this, notice that if $n$ were even,

changing which parent is played first would be equivalent to reversing the entire sequence of games. This means that the probability of a $k$-game win streak at some point is independent of which parent is chosen for the first game.

For the case presented in the puzzle, with $n$ odd:

To earn her allowance, Mary can either achieve a $k$-game streak sometime in the first $n-1$ games, or finish her first $k$-game streak by winning game $n$. Since $n-1$ is even, the probability of achieving a streak in the first $n-1$ games is the same regardless of which parent is played first.

If the winning streak is only achieved at game $n$, that means Mary didn't achieve a streak in the first $n-k-1$ games, lost game $n-k$, then won the last $k$ games. These three events are independent, and the first and third have probabilities independent of which parent is played first. Thus, to maximize the probability of receiving her allowance, Mary should maximize the probability of losing game $n-k$. This game is against the same opponent she played in game 1, so Mary should always start with the stronger opponent.

$\endgroup$
1
  • 3
    $\begingroup$ It is very easy to maximize the probability of losing game $n-k$; just resign on the first move. Is there any better wording you could use there? $\endgroup$
    – mathlander
    Dec 1, 2023 at 23:32
8
$\begingroup$

I'm going to go counter-intuitive and say...

Mary should play the stronger parent first, as that will give her more opportunities to win against them.

In a simplified example, say N = 5 and K = 4. Mary has to win games 2-4, and then either game 1 or game 5. If she plays the stronger parent first, she will have to win the WSW series in the middle (where W = Weaker and S = Stronger) and then can win either the 1st or last game against S... giving her two chances. This way she only has to win 2/3 games against S, and 2/2 games against W which sounds way easier to me.

In a set where N = 9 and K = 4, if she starts with the stronger parent, again she'd have more chances to beat them. She would need to win at least 2/4 (50%) against the weaker parent, but only 2/5 (40%) against the stronger one.

$\endgroup$
2
  • $\begingroup$ But it's not an arbitrary 2/3 games against S, because the middle game has to be won. $\endgroup$ Dec 1, 2023 at 7:56
  • $\begingroup$ Right, but if the middle game is lost, all is lost anyways. The probabilities only matter if the middle game is won. $\endgroup$
    – Stevish
    Dec 1, 2023 at 13:22
1
$\begingroup$

I am giving 3 Solutions.
I think the third Solution ( which is listed in reverse order ) is what Peter Winkler wanted.

SOLUTION 3 :

Let us assume some values. We will later see that these values are almost immaterial.

Assume stronger player $S$ wins with Probability $P1=0.9$ & loses with Probability $Q1=0.1$ , while weaker player $W$ wins with Probability $P2=0.1$ & loses with Probability $Q2=0.9$
Assume White has no advantage.
Assume there is a coin toss for every game to choose White.

Let us take example $k=4$ & $n=7$.

Sequence can be $SWSWSWSWS$
Probability of 4 wins at start is $Q1 \times Q2 \times Q1 \times Q2$
Probability of 4 wins after losing a game is $P1 \times Q2 \times Q1 \times Q2 \times Q1$
Probability of 4 wins after losing 2 games is $P1 \times P2 \times Q1 \times Q2 \times Q1 \times Q2$
Probability of 4 wins after losing 3 games is $P1 \times P2 \times P1 \times Q2 \times Q1 \times Q2 \times Q1$

Sequence can alternately be $WSWSWSWSW$
Probability of 4 wins at start is $Q2 \times Q1 \times Q2 \times Q1$
Probability of 4 wins after losing a game is $P2 \times Q1 \times Q2 \times Q1 \times Q2$
Probability of 4 wins after losing 2 games is $P2 \times P1 \times Q2 \times Q1 \times Q2 \times Q1$
Probability of 4 wins after losing 3 games is $P2 \times P1 \times P2 \times Q1 \times Q2 \times Q1 \times Q2$

Comparing the values , we see that $Q1 \times Q2 \times Q1 \times Q2$ is common , hence we can eliminate that.
We want to then check $(1+P1+P1 \times P2+P1 \times P2 \times P1)$ & $(1+P2+P2 \times P1+P2 \times P1 \times P2)$
Eliminate common terms to check $(P1+P1 \times P2 \times P1)$ & $(P2+P2 \times P1 \times P2)$
Make it $P1(1+P2 \times P1)$ & $P2(1+P1 \times P2)$ & Eliminate common terms
$P1$ versus $P2$

SUMMARY 3 :

Starting with stronger player is better !
Numerical values for $P1$ $P2$ $n$ $k$ do not matter !

SOLUTION 2 :

It might occur that stronger player is always going to win.
The kid is never going to succeed.

SUMMARY 2 :

It is then immaterial who starts.

SOLUTION 1 :

The Question is too vague & we have to make a lot of assumptions.

"choice"

"should she start against the stronger or weaker parent"

I assume (it is reasonable) that there are 2 teams here : "kid" versus "parents"

Kid should "start" or "play white" or "start the game" or "make the opening move" against the stronger player.
That will give the opening advantage when it is required.
Playing black against the weaker player will not matter.

SUMMARY 1 :

The kid makes the choice based on first player of the first game.
When the first game of the "tournament" is between kid and stronger player , kid should make the "choice" to play white.
When the first game of the "tournament" is between kid and weaker player , kid should make the "choice" to play black.

$\endgroup$
6
  • 4
    $\begingroup$ "should she start against the stronger or weaker parent" should be interpreted as "should she choose the stronger or weaker parent to be the first opponent" $\endgroup$ Dec 1, 2023 at 5:24
  • $\begingroup$ What about the choice of playing white ? Is that alternating against the team or alternating against each member or tossing coins ? What if stronger player is going to always win ? There is too much vagueness here , @DanielMathias , which makes it hard to give Concrete Solution. $\endgroup$
    – Prem
    Dec 1, 2023 at 5:49
  • 4
    $\begingroup$ I really don’t see any ambiguity here. The question of whether she should play as white, like that of whether she should develop her bishops early, isn’t germane to what’s being asked. $\endgroup$
    – Sneftel
    Dec 1, 2023 at 7:44
  • $\begingroup$ [[A]] What are your thoughts about Solution 3 , @Sneftel , which I think is what Winkler wanted ? [[B]] The ambiguity about who should start is due to translating as who should play white. That ambiguity is known to Winkler [ & Gardner ] who gave some other Puzzle with these words "Since it is an advantage to play the white pieces (which move first), you alternate playing white and black. A coin is flipped , and the result is that you will be white in the first and third games , black in the second." $\endgroup$
    – Prem
    Dec 1, 2023 at 8:29
  • 1
    $\begingroup$ I also wouldn't say there's any ambiguity here. In context it's pretty clear that its asking who she should start against means who to play against first. $\endgroup$ Dec 1, 2023 at 12:56
1
$\begingroup$

We can prove this using the expected value. Assume Mary plays her mother first. Let $P_m$ be the probability of winning against her mother, and $P_f$ be the probability of winning against her father. Let $k = 2u$. Suppose Mary gets 1 point if she gets an allowance, and 0 if she does not. Then her expected points are:

$$(P_mP_f)^u + (1-P_m)(P_mP_f)^u + (1-P_m)(1-P_f)(P_mP_f)^u+ \ldots+ (1-P_m)^{(n-k+1)/2}(1-P_f)^{(n-k-1)/2}(P_mP_f)^u$$ Swapping $P_f$ with $P_m$ gives her expected points when she plays her father first.

Since it is not immediately obvious which value is greater when $P_m>P_f$ (or vice-versa), we do the following:

$$\frac{\Bbb E(M)+\Bbb E(F)}2 = (P_mP_f)^u\left(1+\left(1-\frac{P_m+P_f}2\right) + (1-P_m)(1-P_f) + (1-P_m)(1-P_f)\left(1-\frac{P_m+P_f}2\right) + \ldots + (1-P_m)^{(n-k-1)/2}(1-P_f)^{(n-k-1)/2}\left(1-\frac{P_m+P_f}2\right)\right)$$ Now, if $P_m>P_f$, $\Bbb E(M)< (\Bbb E(M)+\Bbb E(F))/2$, hence $\Bbb E(M)<\Bbb E(F)$.

So, if her father is the stronger player,

she should play him first.

(and vice-versa)

$\endgroup$
5
  • $\begingroup$ If Pm=1, Pf = 0.5, and n=3, Mary is expected to win 2.5 games when starting against the weaker opponent, but only 2 games when starting against the stronger opponent. Not sure where the error is, but intuitively, Mary should be expected to win more games when playing the weaker opponent more times. The bigger issue is that even if this did maximize the expected number of games won, that's not what Mary is trying to accomplish. $\endgroup$ Dec 1, 2023 at 14:41
  • $\begingroup$ @NuclearHoagie you've completely misunderstood my answer. The line "Suppose Mary gets 1 point if she wins, and 0 if she loses" actually means 1 point if she gets an allowance, and 0 if she does not get the allowance. I will edit the answer to make it clearer $\endgroup$
    – D S
    Dec 1, 2023 at 17:33
  • $\begingroup$ @NuclearHoagie if you will put in your values for $P_f$ and $P_m$, you'll get $\Bbb E(F) = 0.75>\Bbb E(M) = 0.5$ $\endgroup$
    – D S
    Dec 1, 2023 at 17:38
  • $\begingroup$ Maybe I'm missing something, but why is it easier to compare to $\frac{\Bbb E(M)+\Bbb E(F)}2$ rather than $\Bbb E(M)$ and $\Bbb E(F)$ directly? $\endgroup$
    – tehtmi
    Dec 2, 2023 at 19:08
  • $\begingroup$ @tehtmi actually I did that to avoid confusion between ordering $P_m$, $P_f$ and $(1-P_m)$, $(1-P_f)$, as while typing the answer I was making a lot of mistakes. $\endgroup$
    – D S
    Dec 3, 2023 at 11:06
1
$\begingroup$

Mary should play against the

Stronger parent first

This is because

Since $k$ is even Mary will have to play against both parents and equal amount of times. Lets assume the worst case scenario $k=n-1$. In this situation Mary essentially has "a second chances" to win her allowance if she loses the first game but otherwise has "one chance" to win her allowance if she wins the first game. Since if Mary wins her first game she must win her next $k-1$ games and if she loses any then she cannot get her allowance since losing the next game means she has $n-2$ chances to win $k$ times in a row. Using our previous conjecture this is an impossible scenario as Mary cannot win $n-1$ games in $n-2$ tries. However, if Mary loses her first game she still has $n-1$ chances to win $k$ times which we can rephrase as winning $n-1$ games in $n-1$ tries.

In the context of this problem this explains why Mary should play against

The harder parent first. Lets assume Mary can win $p_{1}$ of the time against the weaker parent and $p_{2}$ of the time against the stronger parent when $p_{1}>p_{2}$. Therefore, if Mary plays the weaker parent she has a $p_1 \frac{k}{2} * p_{2} \frac{k}{2}$ chance of winning (since we are in the scenario where she wins the first game). However if Mary plays the Harder parent first and WINS she has a $1*p_1 \frac{k}{2} *p_{2}\frac {k-1}{2}$ and if she loses we are effectively in the scenario where she plays the weaker parent first. By simplifying the equations we get the that playing the weaker parent first results in $ \frac {p_{1}p_{2}k^2}{4}$ and playing the stronger parent best case is $\frac {p_{1}p_{2}k^2-p_{2}k}{4}$ and worst case $\frac {p_{1}p_{2}k^2}{4}$. Since the worst case of playing the stronger parent is the same as playing the weaker parent we would say it doesn't matter who she plays first right? Well since the best case has a lower probability than playing the weaker parent we might as well risk playing the stronger parent first and if it doesn't pay off we still have the chance to play the weaker parent first.

Sorry for the not "mathematical proof" and more of a logic based answer. I'm not a mathematician

$\endgroup$
1
$\begingroup$

I think that

it doesn't matter which parent she plays first. Since k is even, each possible sequence (winning scenario) will have an equal number of plays against the stronger opponent and the weaker opponent. Thus every sequence of k matches has an identical probability of success. The number of such sequences (chances to win) will vary based on the relative values of k and n, but not on which parent is played first.

To expand on my explanation a bit:

Say k=2, and n=3. She has two chances to win. If the weaker parent (W) plays first these two sequences are: WS SW

If the stronger parent (S) plays first then the sequences are: SW WS

But these are the same.

$\endgroup$
3
  • $\begingroup$ This is not correct. Try n = 3 and k = 2. $\endgroup$
    – Simd
    Dec 6, 2023 at 18:45
  • $\begingroup$ This reasoning would be correct if the sequences in question were independent of each other but they are not. Take the sequences where she plays the weaker parent first in the N3K2 case. If she loses a game against the weaker parent that only eliminates one sequence from being a possible success. However, if she loses the game against the stronger parent that eliminates both sequences. $\endgroup$ Dec 6, 2023 at 19:01
  • $\begingroup$ @GoblinGuide Yes, I think you are correct. $\endgroup$ Dec 6, 2023 at 19:10
-2
$\begingroup$

I think that Mary should first play against

the weaker parent.

Because $k$ is an even number, Mary would have to win $k / 2$ games against each parent. Since it would be better for Mary to win sooner rather than later, this strategy would give her a greater chance at winning the initial game, allowing her to continue her streak.

$\endgroup$
4
  • 1
    $\begingroup$ "Since it would be better for Mary to win sooner rather than later" - why? There is no benefit to Mary winning earlier, winning the last 4 of 5 games is exactly as good as winning the first 4 of 5 games. This approach maximizes the probability of winning the first k games but minimizes the probability of winning the last k games - maximizing the probability of an early win doesn't imply maximizing the overall probability of a win. $\endgroup$ Nov 30, 2023 at 16:05
  • $\begingroup$ Sorry if I wasn't entirely clear on what I meant. It just seems that Mary might as well try to win earlier, rather than later, so if she loses a game, she'll have more of an opportunity to build her winning streak again. $\endgroup$ Nov 30, 2023 at 16:52
  • $\begingroup$ @BlueHerring see NuclearHoagie answer for an example of why that doesn't work. $\endgroup$
    – justhalf
    Dec 1, 2023 at 11:41
  • 1
    $\begingroup$ Consider the case where the weaker parent always loses, the stronger has a 1% chance of losing, k is 2, and n is 3. So, Mary has two choices: 1%,100%,1% (i.e., 2 games against the strong parent) or 100%, 1%, 100% (i.e., one game against the stronger parent). At least in this specific example, Mary is better off playing the stronger parent first (1.99% chance of winning 2 games in a row). This does not prove that playing the stronger parent first is optimal. However, this counterexample proves that unconditionally playing the weaker parent first is not optimal. $\endgroup$
    – Brian
    Dec 1, 2023 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.