Can You Solve the Puzzle Which Inspired Probability Theory?

The puzzle below, known as The Problem of Points, is often said to have inspired probability theory.

Fermat and Pascal play a game by repeatedly flipping coins - if a coin lands heads, Fermat gains a point, and if it lands tails, Pascal gains a point. It is agreed that first to $10$ points wins a prize of $100$ francs. Suppose the game abruptly stops when the score is $8$-$7$ to Fermat. How should the prize be fairly divided between the two players?

Post solutions below!

If you would like to be sent a list of our interviews and puzzles each week, sign up to Black Swans here.

Puzzle

· · 4 comments

This sounds quite close in spirit to to the puzzle "Who's Doing the Dishes?".

Tiago ·

True - I think this one is a little easier though.

jdry1729 ·

I'm assuming fair division means split the prize based on win probabilities.

An odd principle, considering if it's taken to the start of the game no one makes any money!

I agree with Tiago that if you can solve the dishes challenge, you can solve this one.

James ·

Hey James - I think your interpretation of fair is most appropriate.

jdry1729 ·

You can solve this with a memoized Python function:

from functools import lru_cache

# probability of Fermat winning, given f heads and p tails
@lru_cache(maxsize=None)
def score(f, p): 
    if f==10:
        return 1
    if p==10:
        return 0
    return .5 * score(f + 1, p) + .5 * score(f, p + 1)

This models the win probability function for Fermat:

$$w(f, p) = \begin{cases} 1 & f = 10 \\ 0 & p = 10 \\ \frac{1}{2} w(f + 1, p) + \frac{1}{2} w(f, p + 1) & 0 \leq f < 10, 0 \leq p < 10 \end{cases}$$

Output:

>>> score(0, 0) # just to test it out
0.5
>>> score(8, 7) # fermat's probability of winning
0.6875
>>> score(7, 8) # pascal's probability of winning (equal to 1 - score(8, 7))
0.3125

So Fermat should get $\$68.75$ and Pascal should get $\$31.25.$

kl2792 ·

If Pascal's score remains $7$ then there is one possibility of Fermat winning, i.e he wins both the next two tosses, with a probability of $0.5\times0.5=0.25$.

If Pascal's score is $8$ when Fermat wins there are $2$ possibilities. Either Fermat loses then wins twice (i.e., LWW) or wins, loses and then wins again (i.e., WLW). Together, these have probability $0.125\times2=0.25$.

If pascals score is $9$ when Fermat wins the game there are $3$ possibilities, LLWW with probability $0.0625$, LWLW with probability $0.0625$ and WLLW with probability $0.0625$.

Adding up all the probabilities of Fermat winning we get $0.6875$. So the probability of Pascal winning is $1-0.6875=0.3125$

The reward should then be divided according to these probabilities.

THamid ·