4
$\begingroup$

The king arrests all married couples where both spouses are PhDs in Math, Computer Science, or Logic. He holds each couple separate from the others and tells each couple in turn that all the rounded-up PhDs will be put on the parade ground in the morning, each with a hat. Each hat will be the same color... OR... one of two colors... the king will not now mention WHICH colors.

Each couple is in a two-person jail cell and has no communication with other couples from the moment of their arrest. Even on the way to the parade ground and on the parade ground, any communication will result in instant death.

When they reach the parade ground the king will raise his sword. At that moment they must all shout out the color of their hat. And they must ALL be right or ALL be wrong... and if wrong must at least name one of the hat colors. Either way the king will set them free! Otherwise he brings his sword down and the firing squad strikes them dead!

What do they say and why?

(This is a generalization of Guessing hat colors. 4 prisoners)

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Do they have to announce one of the colors that the king had chosen like in the other puzzle or could it be any color? $\endgroup$
    – Rick
    Mar 1, 2018 at 8:31
  • $\begingroup$ Thx Rick, I specifically added that and now its gone for some reason--must have forgotten to commit an edit or something. Now fixed. $\endgroup$
    – Swiss Frank
    Mar 1, 2018 at 13:40
  • 1
    $\begingroup$ "He holds each couple separate..." : does this means that the couple won't meet thereafter and they are not allowed to build a collective strategy ? $\endgroup$
    – Evargalo
    Mar 1, 2018 at 14:28
  • $\begingroup$ that was my intention Evargalo... if you can suggest better wording let me know! $\endgroup$
    – Swiss Frank
    Mar 1, 2018 at 19:22
  • 1
    $\begingroup$ @SwissFrank Your wording is good, but it would be better if you strongly emphasized that the PhDs cannot form a plan together, because this is the heart of the puzzle. $\endgroup$
    – Mike Earnest
    Mar 1, 2018 at 22:24

2 Answers 2

Reset to default
10
$\begingroup$

If the PhDs were allowed to plan a strategy together ahead of time, then the following would work:

Everyone guesses based on the assumption that every color appears on an even number of hats.

Unfortunately, the king forbids them from collectively planning. Each couple may come up with a plan that would work if everyone followed it, but how do we know everyone will come up with the same plan?

Fortunately, it turns out this is the unique collective strategy which always works. Therefore, the couples do not have to coordinate; they deduce that the only hope of success is to follow this unique strategy, and as a result all end up doing the same strategy.

Proof:

1. Suppose all the hats are the same, say red. The only winning strategy is to guess red.

2. Suppose all but one of the hats are red and the other is blue. The blue hatted person will see all red hats. For all they know, all the hats are red, so they must guess red to be safe in that case. Since they are wrong, everyone else must guess blue.

3. Suppose there are two blue hats, and the rest are red. Each of the blue hatted people will see all red hats except for one blue hat. For all they know, they are in situation 2, so they must guess blue to be safe. Since they are correct, all the red hatted people must guess red.

 ⋮

The pattern is starting to emerge: no matter what, each person must guess the color they see which appears an odd number of times. You can prove by induction that this holds no matter how many hats of each color appear.

Improve this answer
$\endgroup$
0
6
$\begingroup$

This is just a generalization of the linked question, in which Bass' answer already provides a solution that works with an arbitrary even number of prisoners (which is true for this question, since the king imprisoned couples):

Everyone decides that either there must be an even number of each hat color. They then answer accordingly based on which color is missing from their view (i.e. the color they see an odd number of). This will cause them all to answer correctly or wrongly.

There is another solution, however:

You also didn't specify that they aren't allowed to communicate on the day itself. Each couple can just tell each other what color their hats are, and everyone answers accurately. Yay for loopholes!

Improve this answer
$\endgroup$
4
  • $\begingroup$ Bass's answer is incorrect: read my comment to his answer which I won't repeat hear as it's a spoiler. Besides a "generalization", I've also removed a specific power the original power gave the solver that wasn't necessary, which again spoiler but if you compare you'll see one big thing in the original problem was superfluous. The original problem was very cool and I hope mine isn't seen as so derivative it's stealing. $\endgroup$
    – Swiss Frank
    Mar 1, 2018 at 13:37
  • $\begingroup$ @SwissFrank I couldn't see any flaw in Votbear's answer, so went to see your comment on the original. Your comment to Bass's answer to the other question only mentions a problem with odd N. As Votbear points out, this problem is set up with couples, and so guarantees an even value of N, which means Bass's answer works unmodified. The only relevant additional rule difference I can see is that we cannot communicate our strategy with other couples, so simply have to hope they also figure out (or are aware of) the same strategy. $\endgroup$
    – Steve
    Mar 1, 2018 at 14:23
  • $\begingroup$ @SwissFrank : reading your comment to Bass' answer there, it seems you only point a problem in case $N$ is odd. Your question smartly avoids that case by using couples, so I don't get your point at all... $\endgroup$
    – Evargalo
    Mar 1, 2018 at 14:24
  • $\begingroup$ Votbear did you edit your answer to add the "even" and "couples" or did I somehow mis-read it the first time??? I agree Votbear's got an algorithm that would work, should everyone choose it... But unlike the original puzzle, which requires only "an" algorithm, this puzzle additionally--I think--requires a sketch of why this is the ONLY algo and so therefore we're safe in assuming everyone picks the same one. What do you think? If I worded the puzzle such that a mere algorithm suffices, how should I change the wording? $\endgroup$
    – Swiss Frank
    Mar 1, 2018 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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