This Riddler classic puzzle is about placing bets on baseball:
You are a gambler and a Cubs fan. The Cubs are competing in a seven-game series against the Red Sox — first to four games wins. Your bookie agrees to take any even-odds bets on any of the individual games. Can you construct a series of bets such that the guaranteed outcomes are: You win \$100 if the Cubs wins the series and lose \$100 if the Red Sox win it?
The challenge here is that we don’t know ahead of time when the series will end. It could end in a four-game blowout, or it could last the full seven games. How should we construct our bets so that the result is the same regardless of series length? Here is my solution:
[Show Solution]
The bet we place on a particular game should only depend on the current score in the series, so $X_{ij}$ be the amount we should bet in a best-of-$M$ series if the current score is $i$ to $j$. Let’s look at the $M=5$ case and build our intuition from there:
\[
X = \begin{bmatrix}
X_{00} & X_{01} & X_{02} \\
X_{10} & X_{11} & X_{12} \\
X_{20} & X_{21} & X_{22}
\end{bmatrix}
\]The table only goes up to $\tfrac{M-1}{2} = 2$ since the series ends once a team has won 3 games. If the score is $i$ to $j$, then we either win or lose $X_{ij}$ dollars, depending on who wins the game. But there are many ways to get to a particular score! Suppose for example that the score is currently 2-1. There are three paths from 0-0 to 2-1:
\begin{align}
0 – 0,\, 1 – 0,\, 2 – 0,\, 2 – 1 &; \text{ net winnings: } +X_{00}+X_{10}-X_{20} \\
0 – 0,\, 1 – 0,\, 1 – 1,\, 2 – 1 &; \text{ net winnings: } +X_{00}-X_{10}-X_{11} \\
0 – 0,\, 0 – 1,\, 1 – 1,\, 2 – 1 &; \text{ net winnings: } -X_{00}+X_{01}+X_{11}
\end{align}Our net winnings for each score must be the same for all paths leading there; winnings can only depend on the current score. This allows us to write down many equations that must hold. We will assume that $X_{ij} = X_{ji}$ (symmetry). So whenever the score is tied, our winnings-to-date from all the bets so far must be zero. Starting from the lower-right corner, if the score is 2-2, then the last game decides all, and must therefore be worth \$100. So $X_{22}=100$.
If the score is 1-1, the path to 2-2 must return us to zero. Also, the path to 3-1 must lead to 100. Consequently:
\begin{align*}
X_{11}-X_{21} &= 0 \\
X_{11}+X_{21} &= 100
\end{align*}Solving these equations leads to $X_{11} = X_{21} = 50$. Observe that $X_{21} = X_{12} = \frac{1}{2}X_{22}$ and $X_{11} = \frac{1}{2}(X_{12}+X_{21})$. Interesting!
If the score is 0-0, we can look at pairs of paths that must be equivalent. For example, we have:
\begin{align*}
X_{00}-X_{10} &= 0 \\
X_{10}-X_{20} &=-X_{10} + X_{11} \\
X_{00} + X_{10} + X_{20} &= 100
\end{align*}Rearranging the equations, we obtain:
\begin{align*}
X_{00} &= \tfrac{1}{2}(X_{10} + X_{01}) \\
X_{10} &= \tfrac{1}{2}(X_{20} + X_{11}) \\
X_{20} &= \tfrac{1}{2}X_{21}
\end{align*}This pattern continues, so each entry in the table is the average of the entry to the right and the entry below!
\[
X_{ij} = \begin{cases}
100 &\text{if } i=j=\tfrac{M-1}{2} \\
\tfrac{1}{2}X_{i+1,j} & \text{if only } j = \tfrac{M-1}{2} \\
\tfrac{1}{2}X_{i,j+1} & \text{if only } i = \tfrac{M-1}{2} \\
\tfrac{1}{2}(X_{i,j+1} + X_{i+1,j}) & \text{otherwise}
\end{cases}
\]This recursion is very similar to Pascal’s Triangle, except it starts at the lower-right corner and we are averaging instead of summing. We can build the solution from scratch like this: start with an ordinary Pascal’s Triangle that starts in the lower right, e.g. in the case $M=7$ we have:
\[
\begin{bmatrix}
\color{green}{20} & \color{brown}{10} & \color{orange}{4} & \color{red}{1} \\
\color{brown}{10} & \color{orange}{6} & \color{red}{3} & \color{purple}{1} \\
\color{orange}{4} & \color{red}{3} & \color{purple}{2} & \color{blue}{1} \\
\color{red}{1} & \color{purple}{1} & \color{blue}{1} & 1
\end{bmatrix}
\]Then, look at the colored diagonals, starting from the lower-right corner. Divide them by increasing powers of two: $1$, $\frac12$, $\frac14$, $\frac18$, and so on:
\[
\begin{bmatrix}
\frac{20}{64} & \frac{10}{32} & \frac{4}{16} & \frac{1}{8} \\
\frac{10}{32} & \frac{6}{16} & \frac{3}{8} & \frac{1}{4} \\
\frac{4}{16} & \frac{3}{8} & \frac{2}{4} & \frac{1}{2} \\
\frac{1}{8} & \frac{1}{4} & \frac{1}{2} & \frac{1}{1}
\end{bmatrix}
\]Finally, multiply the whole matrix by 100, and the result is:
\[
\begin{bmatrix}
31.25 & 31.25 & 25 & 12.5 \\
31.25 & 37.5 & 37.5 & 25 \\
25 & 37.5 & 50 & 50 \\
12.5 & 25 & 50 & 100
\end{bmatrix}
\]So, for example, if the score is 2 to 1 in this best-of-7 series, we should bet \$37.50 on the next game. Since the entries of this matrix are simply scaled versions of the entries in Pascal’s Triangle, which can be expressed as binomial coefficients, we can easily come up with a general formula that tells us how much we should bet.
If the score is $x$ to $y$ in a best-of-$M$ series, the bet we should place on the next game (in dollars) is given by the formula:
$\displaystyle
\frac{100}{2^{M-1-x-y}} { M-1-x-y \choose \tfrac{M-1}{2}-x }
$
Roughly, you should bet more as you get closer to the end of the series, and you should also bet more when the score is closer. Here is a visualization of the trend: a plot of how much you should bet on each game in a best-of-41 series (first to win 21 games).
Is it more elegant to know that you have to be at a sum of zero if the series is tied at 3 each, at which time you’d need to bet $100? Then, if you have listed the sample space as a tree, you can just work backwards.
If you want to eliminate some parameters you can just express it as (n C r) / 2^n, where n is the number of games left to play until the championship (aka M-1) and r is the number of games you still need to win. Yours is in the form of the table and obviously equivalent, though.
Oops well r is # of games you need to win minus one, should have fixed that before submitting!