Can You Bet Solely on Your Team’s Record?

Your home team, the Fiddle-delphia Eagles, has two games left in the season. Thanks to time travel you know they will win one and lose the other, but not in which order. You have $100, and before each game you may bet any amount you hold (fractions of a penny allowed) that the Eagles will win: bet $x$ and you gain $x$ if they win and lose $x$ if they lose. With the best strategy, how much money can you guarantee to have after both games, whichever order the results come in?

The Fiddler, Zach Wissner-Gross, August 25, 2023(original post)

The official solution appeared in the post of September 8, 2023 and gives $133.33 for the main puzzle and $827.47 for the Extra Credit. Both agree with the answers below.

Solution

Everything is decided by the first bet. Once the first game is played, the second result is no longer a mystery: it must be the opposite of the first.

Suppose you bet $x$ dollars on the first game. If the Eagles win it, you hold $100 + x$, and you know they will lose the next game, so you bet nothing and keep $100 + x$. If they lose it, you hold $100 - x$, and you know they will win the next game, so you bet everything and double it to $2(100 - x)$.

You do not get to choose which of these happens, so what you can guarantee is the smaller of the two amounts. The first grows with $x$ and the second shrinks, so the smaller one is largest where they meet.

Setting $100 + x = 2(100 - x)$ gives $3x = 100$, so $x = 33\tfrac13$ dollars, and both outcomes then leave you with $$\boxed{\ 100 + 33\tfrac13 \;=\; \$133\tfrac13 \;\approx\; \$133.33. \ }$$ No other first bet does as well: a smaller one leaves less than this if the Eagles win first, and a larger one leaves less if they lose first.

The computation

The check plays the game as a contest against an opponent who picks the order of results to hurt you. With $w$ wins and $\ell$ losses still to come, you choose a bet, the opponent chooses whichever possible result leaves you worse off, and play continues. Write $f(w, \ell)$ for the largest multiple of your money you can guarantee from there. Then $f(0, 0) = 1$, and otherwise $f(w, \ell)$ is the best, over bet fractions $x$, of the worse of $(1 + x)\,f(w - 1, \ell)$ and $(1 - x)\,f(w, \ell - 1)$, where a result that can no longer happen is left out.

The program does not solve for the best $x$ by algebra. It searches for it: the worse of a rising and a falling line has a single peak, so a ternary search, which repeatedly discards the third of the interval that cannot hold the peak, homes in on it. Here $x$ runs from $0$ to $1$, since you may only back the Eagles.

from functools import lru_cache

INF = float("inf")

def worst(x, win, lose):
    """Money left (as a multiple) in the worse of the two
    possible results after betting fraction x on the Eagles.
    A result that cannot happen is ignored (counted as INF)."""
    a = (1 + x) * win if win < INF else INF
    b = (1 - x) * lose if lose < INF else INF
    return min(a, b)

@lru_cache(None)
def f(w, l, both_ways):
    """Largest guaranteed multiple of your money with w wins
    and l losses still to come, in an unknown order."""
    if w == 0 and l == 0:
        return 1.0
    win = f(w - 1, l, both_ways) if w else INF
    lose = f(w, l - 1, both_ways) if l else INF
    lo, hi = (-1.0 if both_ways else 0.0), 1.0
    for _ in range(200):          # ternary search: the worse
        m1 = lo + (hi - lo) / 3   # of a rising and a falling
        m2 = hi - (hi - lo) / 3   # line is unimodal in x
        if worst(m1, win, lose) < worst(m2, win, lose):
            lo = m1
        else:
            hi = m2
    return worst((lo + hi) / 2, win, lose)

print(f"main: ${100 * f(1, 1, False):.2f}")

It prints

main: $133.33

Extra Credit

Now $12$ games remain, and you know the Eagles will win exactly $8$ of them, but not which. You may also bet on either team in each game (bet $x$ on either side and you win or lose $x$). With the best strategy, how much can you guarantee to have after the $12$ games?

Solution

Being allowed to back either side changes the character of the problem. A bet of $x$ on the Eagles is now just a bet with a sign: positive backs the Eagles, negative backs their opponents. The key fact is that every bet is fair in a bookkeeping sense. Whatever you hold before a game, call it $M$, the two amounts you could hold after it are $M + x$ and $M - x$, and these always add up to $2M$.

An upper limit. Imagine, just for counting, that the Eagles could produce any of the $2^{12}$ win and loss sequences, and follow your strategy along each one. After the first game the two branches hold amounts adding to $2 \times 100$. After the second, the four branches add to $4 \times 100$, because each pair of children adds to twice its parent. After all $12$ games, the final amounts over all $2^{12}$ sequences add up to $$2^{12} \times 100 \;=\; 409{,}600 \text{ dollars}.$$ You can never hold a negative amount, so the sequences that really can happen, those with exactly $8$ wins, share at most this total between them. There are $\binom{12}{8} = 495$ of them. If you were guaranteed $G$ dollars on each, they would add up to at least $495\,G$, so $$G \;\le\; \frac{409{,}600}{495} .$$

A strategy that reaches it. The bound is reached exactly when two things hold: every impossible sequence leaves you with nothing, and every possible sequence leaves you with the same amount. That suggests the strategy. At any moment, let $r$ be the number of games still to play and $c$ the number of ways the remaining results could still go (for instance, with $8$ wins and $4$ losses to come, $c = \binom{12}{4} = 495$). Arrange to hold $$M \;=\; \frac{409{,}600}{495} \times \frac{c}{2^{r}} \text{ dollars}.$$ At the start, $c = 495$ and $r = 12$, so $M = 100$, which is what you have. After the next game, the counts of possible continuations in the two branches add up to $c$, and $r$ drops by one, so the two target amounts add up to $$\frac{409{,}600}{495} \times \frac{c}{2^{r-1}} \;=\; 2M .$$ Two targets adding to $2M$ are exactly what one bet produces: back whichever side has the larger target, for the difference between that target and $M$. When one result has become impossible its target is $0$, and the bet is everything on the other side. At the end $r = 0$ and $c = 1$, so you hold $409{,}600/495$ dollars whichever of the $495$ sequences occurred. So $$\boxed{\ G \;=\; \frac{100 \cdot 2^{12}}{\binom{12}{8}} \;=\; \frac{81{,}920}{99} \;\approx\; \$827.47. \ }$$ The same argument gives $2^{m+n}/\binom{m+n}{m}$ times your stake for $m$ wins and $n$ losses in any order. With one win and one loss that is $2$, more than the $\tfrac43$ of the main puzzle, because there you could not back the opponent in the first game.

The computation

The contest from The computation above, now letting the bet fraction run from $-1$ to $1$ so that either side may be backed:

print(f"extra credit: ${100 * f(8, 4, True):.2f}")

It prints

extra credit: $827.47