There is an elegant solution to the problem, which is, at least for me, not easy to come by. I’ll come back to it after I discuss my not-so-elegant solution. If you already discovered the “harder” solution, congratulate yourself, and feel free to ignore the rest of this page.

There are two critical mental steps to take.

First. Think of the process in two stages. \(S_1\): Alice and Bob first toss \(n\) fair coins each, and \(S_2\): Bob tosses one more. The outcome of \(S_1\) conditions the outcome of the second.

Once this first step is taken, then the immediate question is the sample space of \(S_1\). This space most naturally will include pairs of \(n\)-long sequences of Alice’s and Bob’s tosses. At this point, what could be a partitioning set of events given this sample space? We stop and think. The next stage will be a single toss, and at the end of that stage we want to decide whether Bob has more heads or not. Which events might be relevant as a conditioner for this last toss?

  1. If \(S_1\) ends with Alice having more heads, then Bob has no chance to beat her.
  2. If \(S_1\) ends with Bob having more heads, then Bob has no chance to lose.
  3. If \(S_1\) ends with a draw, then Bob has \(1/2\) chance to win.

Observe that these three events partition the sample space of \(S_1\); they exhaust all possibilities and there is not a single outcome in the sample space that would fall in more than one of these events.

The problem, one might think, is that we do not know the probabilities of these three events. All you can hope for is to be able to calculate these probabilities in terms of \(n\), in which case you will still have an unknown. But unknown values do not worry the mathematically oriented. You must go on keeping the hope that you will discover a relation between objects that you don’t know their numerical values.

At this point you have two paths to follow:

  1. Do the calculations for \(n\), which is doable but tedious.
  2. If you can take the second critical step in the reasoning, and see the symmetry in the events partitioning the sample space of \(S_1\), then you can call the probability of the draw event \(x\), and the probability of either Bob or Alice having more heads as \(y\), as Bob’s and Alice’s probabiities are totally symmetric. Your reward for taking this step will be the equality \(2y + x = 1\).

Here is the chance of Bob beating Alice as a result of \(S_2\) conditioned on the outcomes of \(S_1\):

\[P(B) = y\cdot 0 + y\cdot 1 + x\cdot \frac{1}{2}\]

Given that \(2y + x = 1\), we have,

\[P(B) = y + (1- 2y)\cdot \frac{1}{2} = \frac{1}{2}\]

The more elegant (or “Zen mode” solution in Hofstadter’s terms) is to realize that with an odd number of tosses, it will never be the case that Alice and Bob had the same number of heads and tails. Therefore Bob will either have more tails than Alice, or more heads than Alice. As these two cases are equally likely, Bob has more heads than Alice with probability \(1/2\).