4

There is a well known N logicians wearing hats of N colors puzzle:

  1. 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.
  2. The logicians must simultaneously guess a number on their hat.
  3. They win if at least one logician guesses correctly.
  4. 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:

  1. 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.
  2. 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.
  3. They win if all logicians guess correctly.
  4. 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?

klm123
  • 16,216
  • 8
  • 64
  • 125
  • How can such constraints like "the total sum of numbers should be always equal to $\frac{N}{2}$" be followed by the logicians, if they have to simultaneously choose a number? – A. P. Nov 04 '17 at 18:02
  • @A.P. that's the puzzle. – klm123 Nov 04 '17 at 19:53

1 Answers1

1

Of course, you can always reduce the information throughput of the logicians by forbidding them more and more things. The smallest $M_{max}$ that you can reach is $1$. Just enable no one to convey any information, and the only case they can guess right is if all hats are the same color.