A puzzle from This Week’s Finds, Week 250:
You and your friend each flip a fair coin and then look at it. You can’t look at your friend’s coin; they can’t look at yours. You can’t exchange any information. Each of you must guess whether the other person’s coin lands heads up or tails up. Your goal, as a team, is to maximize the chance that you’re both correct.
What’s the best you can do? If you pick an answer at random, you’ll get it right 1/4 of the time; can you prove that that’s the best you can do? If not, can you find something better?
Post Revisions:
There are no revisions for this post.
Posts
4 possibilities, xy = HH, HT, TH, TT.
What we want is functions g(x) and h(y) such that P(g(x)=y && g(y)=x) is maximized.
h(x)=x, g(y)=y give cases
coins guesses
xy g(y)h(x)
HH HH — correct
HT TH — incorrect
TH HT — incorrect
TT TT — correct
So guessing that your partner’s coinflip matches yours results in a 50% success rate. So does guessing that your partner has the opposite.
It is easy to see that this cannot be improved because even if your partner is perfect, you must guess wrong at least 50% of the time.
4/29/2007 @ 9:02 pm