Here's a general proof that's similar to Jimmy He's, but uses a different principle to produce a bijection between wins and losses. It's less succinct and elegant than some other proofs here, but I think it reveals some interesting details about the way the extra toss affects the results. (Note also that this treats Heads as winning, rather than tails!)
First, player A tosses the coin n times; then player B tosses it n + 1 times. That makes a total of 2n + 1 tosses. Instead of treating these as separate turns, let's treat them as a partitioned sequence. For example:
\begin{align*}
\mathrm{HTTHHTH} \mathrm{HHTHHTTH}\ -> \mathrm{HTTHHTH}\ \ |\ \ \mathrm{HHTHHTTH}
\end{align*}
We can then determine the winner by asking whether there are strictly more heads after the partition than before. (In the above case, we have 4 and 5, and player B wins.) Now, what happens when we reverse the sequence? Crucially, there is an asymmetry: players swap all values except for the first one after the partition. I'll call this the asymmetrical value. Here are the relevant cases that cover all possibilities evenly.
- The number of heads after the partition is greater than the number of heads before the partition by 2 or more.
- There is one more head after the partition than before, and the asymmetrical value is a $\mathrm{T}$.
- There is one more head after the partition than before, and the asymmetrical value is an $\mathrm{H}$.
- There are an equal number of heads before and after the partition, and the asymmetrical value is a $\mathrm{T}$.
- There are an equal number of heads before and after the partition, and the asymmetrical value is an $\mathrm{H}$.
- The number of heads after the partition is strictly less than the number of heads before.
In cases 1, 2, 5, and 6, rotation always turns winners into losers, thus creating a bijection in those cases. In case 1, the asymmetrical value doesn't matter because player B's lead is so big; rotation always passes a winning count to player A. Likewise, in case 6, the asymmetrical value doesn't matter because player A's lead is so big.
In case 2, the asymmetrical value doesn't matter because it is a $\mathrm{T}$, so it doesn't affect the counts; player B's lead is transferred to player A. In case 5, the asymmetrical value does matter; it stays with player B upon rotation, and as a result, a loss for B (equal heads on both sides) turns into a win for B (two more heads after the partition than before).
Finally, we have cases 3 and 4. In these cases, we can't create a bijection directly because of the asymmetrical value. In case 3, player B has the lead, and maintains it after reversal because the asymmetrical value (an $\mathrm{H}$ in this case) doesn't change hands. In case 4, the counts are equal, making player A the winner; the asymmetrical value is a $\mathrm{T}$ so it doesn't affect the count upon reversal, and A still wins.
Here, instead of creating a bijection between reversals, we create a bijection between the two cases. In both cases, the counts on either side of the asymmetrical value are equal, so every case 3 sequence can be converted into a case 4 sequence by changing the asymmetrical value, and vice versa. When the asymmetrical value is a $\mathrm{T}$, A wins; when it's an $\mathrm{H}$, B wins.
That last move is similar to the "tiebreaker" move that other proofs have offered, but I think this approach shows how that tiebreaker works in a more detailed way.
range(0, end)
. Python automatically starts the range generator at 0; you can just dorange(end)
. $\endgroup$ – rookie Jan 31 '14 at 14:47