Tag: counting

Let’s consider a more general version of the game. Let $f(n,m)$ to be the expected number of competitors that make it across the bridge assuming there are $n$ total competitors and the bridge has $m$ unknown tiles remaining. If there are no competitors, then clearly none can make it across. Also, if there are no unknown tiles remaining, then all competitors make it through. This leads to the boundary conditions
\begin{align}
f(0,m) &= 0\quad\text{for }m=0,1,2,\dots \\
f(n,0) &= n\quad\text{for }n=0,1,2,\dots
\end{align}Now consider the general case with $n$ competitors and $m$ bridge tiles. Each time a competitor takes a turn, they will cross some number of tiles before they are eliminated. Let’s look at the possible cases for the first competitor.

• With probability $1/2$, they are eliminated on the first tile. So the $n-1$ remaining competitors only have to contend with $m-1$ unknown tiles.
• With probability $1/4$, they are eliminated on the second tile. So the $n-1$ remaining competitors only have to contend with $m-2$ unknown tiles.
• Continuing in this fashion, with probability $1/2^m$, they are eliminated on the last (the $m^\text{th}$) tile, and the $n-1$ remaining competitors have $0$ unknown tiles to deal with.
• Finally, with the remaining probability of $1/2^m$, the competitor guesses all tiles correctly, which means that all $n$ competitors will get across safely.

We can express these statements concisely in the following recursion.
\[
f(n,m) = \sum_{k=1}^m \frac{1}{2^k} f(n-1,m-k) + \frac{n}{2^m}
\]One way to simplify this expression is to multiply both sides by $2^m$ and define $g_n(m) := 2^m f(n,m)$. Then, the recursion becomes
\begin{align}
g_0(m) &= 0 \\
g_n(m) &= n + \sum_{k=0}^{m-1} g_{n-1}(k)\quad\text{for }n=1,2,\dots
\end{align}Applying this recursion for the first several steps, we obtain
\begin{align}
g_1(m) &= 1\\
g_2(m) &= 2+m\\
g_3(m) &= \tfrac{1}{2}(6+3m+m^2)\\
g_4(m) &= \tfrac{1}{6}(24+14m+3m^2+m^3)\\
g_5(m) &= \tfrac{1}{24}(120+70m+23m^2+2m^3+m^4)\\
g_6(m) &= \tfrac{1}{120}(720+444m+120m^2+35m^3+m^5)\\
g_7(m) &= \tfrac{1}{720}(5040+3108m+1024m^2+135m^3+55m^4-3m^5+m^6)\\
g_8(m) &= \dots
\end{align}From there, we can recover the expected number of winners via $f(n,m) = g_n(m) /2^m$. Although computing each subsequent function is straightforward, I could not find a closed-form expression for $g_n(m)$. Each is a polynomial of degree $n-1$, but beyond some obvious observation such as the constant term being $n$ and the common denominator being $(n-1)!$, I couldn’t find a general formula.

For the specific instance ($n=16$ and $m=18$) described in the problem statement, we can obtain the exact expected number of winners, and it is

$\displaystyle
f(16,18) = \frac{458757}{65536} = 7.0000762939453125 \text{ (exact)}
$

which is slightly larger than $7$.

Approximate (asymptotic) solution

We can approximate $f(n,m)$ as follows. Each tile will eliminate on average $\frac{1}{2}$ of a contestant. So if we start with $n$ contestants, roughly $n-\frac{1}{2}m$ contestants will cross the bridge. This leads to the approximation

$\displaystyle
f(n,m) \approx n-\tfrac{1}{2}m
$

This approximation doesn’t work when the number of contestants is small. For example, if $n\lt \frac{1}{2}m$, it would lead to a negative number of contestants crossing the bridge, which is of course impossible. But the approximation turns out to be pretty good when $n$ is larger. Applying the approximation to the specific instance in the problem statement, we find $f(16,18) \approx 16-\tfrac{1}{2}\cdot 18 = 7$, and this is very close to the true solution!

Here are some plots that confirm the formula; I plotted $f(n,m)$ for fixed values of $n$ and $m$.

This solution comes courtesy of comments by Guy D. Moore and MarkS.

As in the previous solution, suppose we have $n$ contestants and $m$ bridge tiles. Suppose $b$ tiles are broken during the course of the game. This occurs with probability $\frac{1}{2^m}\binom{m}{b}$, since each tile has a probability of $\frac{1}{2}$ of being guessed incorrectly. When $b$ tiles are broken, $n-b$ contestants cross the bridge. Finally, we can break at most $\min(n,m)$ tiles, since there are only $m$ tiles, and each of the $n$ players can break at most one tile. Therefore, the expected number of competitors to make it across the bridge is:

$\displaystyle
f(n,m) = \frac{1}{2^m}\sum_{b=0}^{\min(n,m)} \binom{m}{b}(n-b)
$

If the special case where $n\geq m$, the sum will go up to $m$, and we can evaluate it exactly, by writing:
\begin{align}
(1+x)^m &= \sum_{b=0}^m \binom{m}{b} x^{m-b} \\
x^{n-m}(1+x)^m &= \sum_{b=0}^m \binom{m}{b} x^{n-b} \\
(n-m)x^{n-m-1}(1+x)^m + m x^{n-m}(1+x)^{m-1} &= \sum_{b=0}^m \binom{m}{b} (n-b)x^{n-b-1}
\end{align}where in the last step, we differentiated both sides with respect to $x$. Now, setting $x=1$ on both sides and dividing by $2^m$, we obtain:
\[
\frac{1}{2^m}\sum_{b=0}^m \binom{m}{b} (n-b) = n-\frac{1}{2}m
\]So the “asymptotic” solution I found in my first solution isn’t just asymptotic; it’s exact when $n\geq m$.

When $n\lt m$, there is no closed-form expression for the sum. However, we can be smart about how we evaluate it. Since we know the sum of all $m$ terms, we only have to evaluate $\min(n,m-n)$ terms. This leads us to the complete solution:

$\displaystyle
f(n,m) = \begin{cases}
n-\frac{1}{2}m & \text{if }n \geq m \\
\frac{1}{2^m}\sum_{b=0}^n \binom{m}{b} (n-b) & n\lt m\\
n-\frac{1}{2}m-\frac{1}{2^m}\sum_{b=n+1}^m \binom{m}{b} (n-b) & n \lt m\text{ (alt.)}
\end{cases}
$

Interesting side-note

Guy D. Moore also pointed out that there is a simpler recurrence relation for $f(n,m)$, given by:
\[
f(n,m) = \frac{f(n,m-1) + f(n-1,m-1)}{2}
\]Using this recurrence with the generating function
\[
G(x,y) = \sum_{n=0}^\infty \sum_{m=0}^\infty f(n,m) x^n y^m,
\]it is possible to show that:
\[
G(x,y) = \frac{x}{(1-x)^2}\cdot \frac{2}{2-y(x+1)}
\]Therefore, $f(n,m)$ is the coefficient corresponding to the $x^n y^m$ term in the series expansion of $G(x,y)$ above! Here is an example of this working for $n=16$ and $m=18$ (as in the original problem) using WolframAlpha.

Suppose our cards have values $\{1,2,\dots,n\}$ and the deck contains $m_i$ cards with value $i$. The total number of cards in the deck is equal to $m = m_1 +\dots+m_n$, and we assume $m$ is even so that the deck can be evenly split in half. In a standard deck of playing cards, we have $n=13$ and $m_1=m_2=\dots=m_n = 4$.

Rather than thinking about “how many games we would expect to play before I had a flawless game”, let’s instead work out the probability that a game of War will be flawless for me (I wins in $m/2$ turns with no ties). This is a counting problem: how many ways are there of arranging the cards in the deck so that I win flawlessly?

To this effect, define $f(m_1,\dots,m_n)$ to be the number of ways I can win flawlessly if the cards remaining have distribution $(m_1,\dots,m_n)$. We will develop a recursive formulation of $f$.

If I pick “$i$” in the first round, I will win the round with no tie if my opponent picks “$j$” with $j \lt i$. This can happen in $m_i m_j$ ways, and then I can win the remaining rounds flawlessly in $f(\dots)$ ways, where the arguments $m_i$ and $m_j$ are each decremented by $1$. Therefore, we can write:
\[
f(m_1,\dots,m_n) = \sum_{1 \leq j \lt i \leq n} m_i m_j f(m_1,\dots,m_j-1,\dots,m_i-1,\dots,m_n)
\]We also have the terminal condition $f(0,\dots,0)=1$, for if we ever achieve this condition, there are no cards left and we have won!

We can make two critical observations that will greatly simplify computation of $f$:

• We can prune out any zero entries. For example, $f(0,2,0,4,0,0) = f(2,4)$. This follows because when a particular card number is not present in the deck, we may relabel the numbers on the cards and simply skip over the missing number.
• We can rearrange arguments. For example, $f(6,4,1,7) = f(1,4,6,7)$. This is due to the fact that our recursive equation is symmetric in the arguments (all pairs of indices are included in the sum and contribute similarly to the count) and our base case $f(0,\dots,0)$ is symmetric as well.

Equipped with these tools, we can write very efficient code to compute the solution for the case of a standard deck of cards. Here is an efficient recursive implementation in Python that computes the solution for a standard deck of cards.

from itertools import combinations

def memoize(f):
    memo = {}
    def helper(x):
        # prune zeros and sort!
        y = tuple( sorted([z for z in x if z > 0]) )
        if y not in memo:
            memo[y] = f(y)
        return memo[y]
    return helper

@memoize
def winning_hands(counts):
    N = len(counts)    
    if N == 0:  # base case (no cards left in the deck)    
        return 1
    
    out = 0
    for i1,i2 in combinations(range(N),2):
        tmp = list(counts)
        tmp[i1] -= 1
        tmp[i2] -= 1
        out += counts[i1] * counts[i2] * winning_hands(tmp)
    return out

winning_hands( 13 * [4] )

The code took about 100ms to compute the answer:
\[
252656585660288881535364185959261220490470307542335488000000
\]

We can divide this by the total number of hands (which is $m!$) to obtain the probability of winning flawlessly.

from math import factorial
from fractions import Fraction

Fraction( winning_hands(13 * [4]), factorial(52) )

And the result is:
\begin{align}
p &= \mathrm{Prob}(\text{flawless win}) \\
&= \frac{93686147409122073121}{29908397871631390876014250000} \\
&\approx 3.132436\times 10^{-9}
\end{align}

This is a very small number, but the more we play, the likelier we are to win. To quantify this, suppose we play $N$ games. The probability that we win flawlessly at least once is $1-(1-p)^N$. We can plot this as a function of $N$ to see how it grows:

So to have a $50\%$ chance of winning flawlessly at least once, I would have to play around 220 million times. To have a $95\%$ chance of winning flawlessly at least once, I would have to play around 1 billion times. Needless to say, that’s a lot of war.