8
$\begingroup$

At the 2020 yearly black- and white- hatted logician gathering, the following fun activity is organized.

$N$ logicians will sit around a table, each wearing a black or a white hat the color of which is chosen for them randomly at the flip of a fair coin. Everybody sees the other hats but ignores the color of his own.

Every 15 seconds a bell rings and the logicians must immediately do one of 3 actions: say "black", say "white" or say nothing.

If at any time a logician claims a color that is not the color of his hat, the building collapses and they all die in great pain. They know how to have fun.

When all logician have correctly claimed the color of their hat, the game concludes and they are served a delicious meal.

If one or more logicians can't make up their mind and never say anything, well, they all die first of boredom figuratively and then of hunger literally.

They can discuss freely to decide a strategy before the game starts. But once it has started and the hats get chosen, the communication is limited to seeing the other's hats colors and hearing the other's answers.

Can they guarantee too all survive? If not, how can they maximize the probability to survive and eat the delicious meal? Assume $N$ is large.

$\endgroup$
7
$\begingroup$

A strategy:

The logicians count how many black hats they see. If that many ticks pass and nobody has called anything, they call "black". If a group of people has called "black", the remaining logicians call "white" on the next turn.

This works as long as

there is at least one black hat.

If there is one black hat, the person will call "black" after 0 ticks. Everyone else sees 1 black hat, so they prepare to call "black" on turn 2, but then they get preempted and so they call "white" and win.

If there are two black hats, those two people notice that nobody called "black" on turn 1, so they call "black" on turn 2. The white-hatted players saw two black hats and were each preparing to call "black" on turn 3; once the black-hatted players leave, the white-hatted players switch to "white".

If there are three black hats, the three people will call "black" on turn 3, and the remainder (who were planning to call "black" on turn 4) will now call "white" instead.

This continue for any number of black-hatted players: it is essentially the solution to the classic Blue Eyes problem.

This is optimal because:

Let's say you have a strategy. Among all possible hat configurations, consider the first day $d$ that someone makes a call. Look at a configuration where someone calls on day $d$: since there is no difference in the things the caller sees up until that point, they have not learned anything about their own hat from the other players' actions. So there must be at least one case where this person guesses wrong.

Therefore there is no perfect strategy: the best possible strategy is one that works in all but one case. The strategy I gave works in all cases except the "fully white" case, so it is optimal.

| improve this answer | |
$\endgroup$
  • $\begingroup$ That is exectly what I had in mind. And congratulations for your 100k rep. $\endgroup$ – Florian F Jul 18 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.