3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – A. P. Nov 4 '17 at 18:02
  • $\begingroup$ @A.P. that's the puzzle. $\endgroup$ – klm123 Nov 4 '17 at 19:53
1
$\begingroup$

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.

$\endgroup$

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.