50th Putnam 1989

Problem A4

A player plays the following game. At each turn a fair coin is tossed (probability 1/2 of heads, and all tosses independent), and, depending on the results of the tosses to date, (1) the game ends and the player wins, (2) the game ends and the player loses, or (3) the coin is tossed again. Given an irrational p in the interval (0, 1), can we find a rule such that (A) the player wins with probability p, and (B) the game ends after a finite number of tosses with probability 1?



Answer: yes.

Let the binary expansion of p be 0.p1p2p3 ... . The coin is tossed repeatedly until it comes up heads. If the first heads is on toss n then the player wins iff pn = 1.

Note that the prob that the game ends after toss n is 1/2n. So the probability that the player wins is ∑pn/2n = p, as required.

Finally, the probability that the game requires more than n tosses is 1/2n, so the probability that only finitely many tosses are required is 1.



50th Putnam 1989

© John Scholes
1 Jan 2001
Last corrected/updated 2 Dec 02