7
$\begingroup$

1000 logicians standing in a circle are blindfolded and a hat of either black or white color is placed on each person's head. The blindfolds are then removed and each person can now see everybody's hat color but his own. After exactly one minute, they all have to simultaneously guess their own hat color.

No communication in any form is allowed after the hats have been placed. However, before the hats are placed, the logicians are allowed to gather and devise a strategy for maximising the number of correct guesses.

Questions :

  1. What should be their strategy to get the maximum guaranteed correct guesses?

  2. Had the total number of different hat colors been three instead of two, then what strategy should they have devised to get the maximum guaranteed correct guesses?

P.S: I do not know the answer of this puzzle but I have been wondering about the answer for very long . It is based on a similar well known puzzle with infinite hats where the aim is to make only a finite number of incorrect guesses. The infinite version and it's solution can be read here : https://tinyurl.com/infinitehats

$\endgroup$
  • $\begingroup$ Note: They are superhuman logicians and for them, having just 1 minute is more than enough to see all the 999 hat colors around them and then come up with their answer using the most optimal strategy that exists . $\endgroup$ – Hemant Agarwal Feb 18 at 5:28
  • $\begingroup$ Just to clarify: the hats are not evenly split between black and white right? They could be 999 B and 1 W, or 500 and 500, correct? $\endgroup$ – SilverCookies Feb 18 at 14:06
  • $\begingroup$ @silvercookies ..The hats are randomly placed ..So there could even be 1000 black and 0 white hats. $\endgroup$ – Hemant Agarwal Feb 18 at 14:16
  • $\begingroup$ This puzzle can be solved with a slight adjustment to the solution to this puzzle. I'm not sure whether that's enough to make it a duplicate. $\endgroup$ – Acccumulation Feb 27 at 16:05
10
$\begingroup$

Here is a way to guarantee 500 correct guesses.

Beforehand they split into two groups of 500. One group will assume that the number of black hats is odd, the other that the number of black hats is even. After the hats are placed they determine whether their own hat is black, given their assigned assumption. One of the groups will use a correct assumption and will all get their colours correct, the other group will be all wrong. This method therefore gives exactly 500 correct guesses every time.

Edit:

The above is optimal, because the expected value of random guessing is 500, and with no extra information given to the logicians about how the hat colours are chosen, this cannot be raised. The only thing their strategy can change is the variation, and a variation of zero is optimal.

For the second question, using three colours of hats:

A guaranteed 333 correct guesses is possible.
Label the three colours by the numbers 0,1, and 2.
They split into three groups of 333 (and one left over who doesn't take part). One group assumes that the sum of all the hat colours is divisible by 3, one group that it gives a remainder of 1 when divided by 3, and the last that it has remainder 2 when divided by 3.
Exactly one of those three assumptions must be true.
Every person can work out their own hat colour given their assumption, so the group whose assumption is true will give all correct guesses. The other groups will all guess wrongly (and the person left over might guess wrong too).
So there are guaranteed to be 333 correct guesses.
This is optimal for the same reason as the two-colour version.

Edit 2:

As @Acccumulation pointed out in a comment, in practice it is much easier to split the 1000 people into smaller groups, each of which then apply the solution strategy outlined above. That way they only need to look at the hats in their own small group instead of at all the hats.

So for two colours we have 500 pairs of people, and in each pair one assumes their hats will be the same colour (i.e. that there are an even number of black hats), the other that their hats will be different (i.e. an odd number of black hats).
Similarly, with three colours of hats there could be 333 groups of three people, each person in a group using a different assumption w.r.t. the sum of their trio's hat colours modulo 3.

$\endgroup$
  • $\begingroup$ I feel that this method indeed gives guaranteed 500 correct guesses for the first question . Let us now see if someone can better this . Also still waiting for an answer to the second question. $\endgroup$ – Hemant Agarwal Feb 18 at 17:36
  • $\begingroup$ Excellent answer, clean and clear. Also compelling proof that the answers are optimal. $\endgroup$ – user3294068 Feb 19 at 21:06
  • $\begingroup$ How do you respond to Matthew Barber's answer in guessing the hat that they can see the most of? Does it still sum to 0? (i.e., of all configurations with 500 black and 500 white, the loss there is exactly the same as the gain from getting the 500+N black and 500-N white) $\endgroup$ – justhalf Feb 19 at 23:58
  • $\begingroup$ The mean in my method sums to just shy of 750,assuming equal distributions, so you can significantly beat guesswork in the N=1 to 500 range. Unfortunately, the extra information it uses, i.e. the number of visible hats, won't be of any extra use in the N=0 case, so 500 is indeed the best guaranteed correct answers overall. It might be possible to devise a strategy that uses both the number of visible hats and divides the logicians into parity groups to get both 500 in the middle and improved results in the wings. One for the Hamming code buffs, perhaps? $\endgroup$ – Matthew Barber Feb 20 at 4:30
  • 1
    $\begingroup$ @justhalf For example, with 8 logicians instead of 1000, there are $2^8=256$ possible hat assignments. Of these, $2$ assignments result in $8$ correct guesses (all white or all black), $16$ result in $7$ correct guesses, $56$ in $6$ correct, $112$ in $7$ correct, and finally $70$ in $0$ correct. This gives an expected value of $(2*8+16*7+56*6+112*5+70*0)/256 = 4$, as expected. $\endgroup$ – Jaap Scherphuis Feb 20 at 9:48
5
$\begingroup$

First, I'd note three things:

  1. The usual solution to the hat puzzle cannot be used, since the guesses must be made simultaneously, meaning nobody could pass on any information to the other players their guess.
  2. With only a minute to count 1000 hats, you wouldn't have enough time to work out a definite answer by elimination, even assuming you knew the totals in advance.
  3. You would have enough time to count a fairly large sample which, if selected sufficiently at random, ought to give you a fairly accurate estimate of the overall populations. Hopefully, being logicians, they'd know how to do this.

Bearing that in mind, my strategy would be:

They could all give the answer as the hat they can see the most of. That way, in aggregate, they'll at least beat random guesswork. For instance if there are 600 black hats and 400 white ones, they'll be correct 60% of the time rather than just 50%, with the accuracy rising to nearly 100% if there's a high proportion of one over the other.

The worst case is when it's 500 of each, where everyone will see slightly more of the hat that isn't their own. However, its unlikely that everyone could count to such accuracy so the results should still be about as good as guesswork in that limit.

The strategy remains the same if there are more kinds of hat added; just keep going with the one that has the highest count.

$\endgroup$
  • $\begingroup$ I have added a comment to my question after reading your answer. They are all superhumans and 1 minute of time does not hinder them in anyway to use the most optimal strategy that exists. $\endgroup$ – Hemant Agarwal Feb 18 at 5:29
2
$\begingroup$

Assuming:

The colour of each hat is picked randomly from the available colours with equal chance of it being either colour (e.g. 50% for 2, and 33.3% for 3 different colours).

Then:

Once they've counted the total of hats of each colour on all other heads, then there is a higher chance of them having the colour that has the least amount.
E.g if there are 499 white and 500 black, then they are more likely to have a white hat.
In the case of the 3 colours this breaks down if the total is exactly 333 in each direction, as one colour will need 334 to round it up, but if the outcome is not actually evenly spread (e.g 331, 333, 335) then the strategy still holds for being one of the lowest counted colours.

However:

I believe this falls into the common misconception that if you have flipped 10 coins in a row and they've all been heads, then the next one has a higher chance of being tails. Which is obviously wrong as it will continue to be a 1 in 2 chance.
In this case, the chance of your hat being a specific colour is still that 1 in 2 or 1 in 3, despite what everything else is.

Therefore:

I believe there is no such strategy that can maximise this, given my assumption.

$\endgroup$
  • $\begingroup$ Note that the question explicitly asks for a strategy that gives the maximum "guaranteed" correct guesses. According to your answer , the maximum guaranteed correct guesses is 0 for both questions 1 and 2. However, 0 is not the correct answer . $\endgroup$ – Hemant Agarwal Feb 18 at 11:03
  • $\begingroup$ @HemantAgarwal then without knowing the number of hats of each colour, there is no guarantee that anyone can get it right. $\endgroup$ – AHKieran Feb 18 at 12:44
  • $\begingroup$ @AHKieran you are wrong, the other answers do indeed give a guaranted number of correct guesses. Also, even giving your assumptions, seeing fewer hats of one color does not increase the chance or your hat being the rare color $\endgroup$ – SilverCookies Feb 18 at 14:18

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.