I expect that when the count is close enough to 50-50, each individual maximizes their chance of being right if they guess the *opposite* of the color that constitutes the majority (if any) of what they see. —Dan -----Original Message-----
From: James Propp <jamespropp@gmail.com>
(I remember the days of putting in ^L ^L ^L at the top of an email before posting a spoiler. Is there something comparable that works for modern email readers?)
The prisoners can achieve a probability of success exceeding 90% if each person sees which color predominates among the 99 hats that he sees and then guesses that his hat is that same color. This only fails when there's a 50-50 split, which happens about 8% of the time.
I believe that this is best possible, but I don't have even the beginnings of a proof.
On Sun, Jun 18, 2017 at 1:42 PM, Thane Plambeck <tplambeck@gmail.com> wrote:
(1) (via Peter Winkler) Here's a (seemingly) new hat puzzle for you:
100 prisoners will be fitted with red or blue hats according to fair coinflips. Then the lights are turned on; each prisoner sees every other hat color and must write down a guess for his own. If a majority (at least 51) get their own hat color right, all the prisoners will be freed.
As usual the prisoners can't communicate once the hats are placed, but have time to strategize beforehand. Can they achieve a 90% probability of being freed? How about 95%?
(2) (Johan Wästlund) I'll just throw in here a question of (what turns out to be) similar flavor: Suppose you play a type of one-person tic-tac-toe where in every "move" you select a set of unoccupied squares, and then flip a coin to decide whether you get all those squares, or your "opponent" gets them. What winning probability can you achieve?