[borisp]

Maybe this problem has been posted before, but here it is anyway. It is a basic example of more general principles involved in the theory of quantum computing; I found in on John Baez's blog (a physics prof at one of the UC's).

You and a friend are each going to flip a fair coin, simultaneously. You each get to look at the result of your flip, and then you each have to guess about the outcome of your friend's flip. No communication is allowed during the whole process, but you can discuss strategy beforehand. You "win" if you both guess correctly, otherwise you "lose." What is the best probability of "win" that you can achieve?

(Specifically, I am posting this problem because it tangibly illustrates the difference between the notions of "guessing the outcome" and "probability." The confusion between the two seems to be the origin of the Sleeping Beauty "paradox.")