March 31, 2018
PART ONE [a warden prisoner hats puzzle (there are a million of these)]: three prisoners are each given a hat, which is either red or blue. They can each see all the other hats, but nobody can see their own. They cannot communicate in any way once the hats are on. After they see each other, the prisoners are separated, and each is privately asked what color hat they are wearing. Prisoners can respond red, blue, or unsure.
1) If anyone guesses wrong, they all lose.
2) If everybody says “unsure,” they all lose.
3) [last possibility] If at least one person guesses correctly and nobody guesses incorrectly, they all win.
They can strategize beforehand as much as they want, but once the game starts they cannot communicate in anyway.
Find a strategy where they win at least 65% of the time. (Hint: “65” is not best possible)
PART TWO: now suppose there are 7 prisoners. Find a strategy that wins at least 80% of the time (Hint: “80” is not best possible).