There is a well known N logicians wearing hats of N colors puzzle:
- N logicians are wearing hats with numbers from 1 to N (each hat has one number; there can be multiple hats with the same number). Each logician can see the numbers on all hats except his own.
- The logicians must simultaneously guess a number on their hat.
- They win if at least one logician guesses correctly.
- How to do it if they can agree on a strategy beforehand?
Now let's say we want all of the participants to guess correctly. In order to do that we allow them to exchange information before guessing:
- N logicians are wearing hats with numbers from 1 to M (each hat has one number; there can be multiple hats with the same number). Each logician can see the numbers on all hats except his own.
- A. The logicians must simultaneously chose a number, which must be 0, 1, 2 or 3. And then call it out.
B. Then, knowing who said what, logicians must simultaneously guess a number on their hat. And call it out.- They win if all logicians guess correctly.
- How to do it if they can agree on a strategy beforehand?
Each logician here gives 2 bits of information to others and you can solve this puzzle for $M$ up to $4^{N-1}$. You can reduce $M_{max}$ to $2^{N-1}$ easily, by making constraint at step 2.A. stronger and allowing them to call out only 0 or 1.
I wonder, can you make $M_{max}$ smaller than $2^{N-1}$ with even stronger constraints? Like "2.A. Each one calls out either 0 or 1, but total sum of numbers should be always equal to N/2, or you lose".
Meanwhile, of course, the solution still should be possible and all logicians must obey the same rules.
What is the smallest $M_{max}$ here?