The puzzle below, known as The Problem of Points, is often said to have inspired probability theory.
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.
The puzzle below, known as The Problem of Points, is often said to have inspired probability theory.
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.
This sounds quite close in spirit to to the puzzle "Who's Doing the Dishes?".
True - I think this one is a little easier though.
Hey James - I think your interpretation of fair is most appropriate.
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.$
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.