Either you’ll toss more heads than I do or you’ll toss more tails than I do, but not both. (Right?) These outcomes are symmetric, so each has probability 1/2.

UPDATE: A number of readers questioned the validity of this solution, but I think that’s due to a bad writeup on my part. I don’t know who devised the problem originally; I found it in the 1995 collection Five Hundred Mathematical Challenges, by Edward Barbeau, Murray Klamkin, and William Moser. Here’s their presentation:

John tosses 6 fair coins, and Mary tosses 5 fair coins. What is the probability that John gets more “heads” than Mary?

More generally, suppose John tosses n + 1 coins and Mary tosses n coins. Then, either John tosses more heads than Mary does or John tosses more tails than Mary does — but not both. (Check this out!) Since these two outcomes are symmetric, each occurs with probability 1/2.

I think I confused the issue by failing to note that this reasoning addresses specifically the case of n coins vs. n + 1. I still haven’t had time to think about this carefully, but most of the people who’d objected wrote back later to change their minds. If you still think it’s incorrect, please do let me know, and I’ll post further updates here. Sorry for the confusion, and thanks to everyone who’s written in.

UPDATE #2: Yes, the solution appears to be valid with this change. Thanks to everyone who contributed!