4
$\begingroup$

This question already has an answer here:

N > 1 people sit in a circle clearly seeing all others. They are going to be blindfolded and, while in this state, hats are put on their heads - one per person, naturally. On each hat there is written a number from 0 to N-1. The numbers may be different or some may be equal. Nothing is known about that, except that each is picked up from the set {0, 1, 2, ..., N-1}. When blindfolds are removed the numbers are in full display: everyone sees all the numbers except one's own. Each is tasked with guessing his number. They are not allowed to communicate in anyway. Each is given a piece of paper on which to write his guess. The papers are collected and the responses are examined. The team wins if there is at least one right guess.

This is the puzzle. But there is one more stipulation: before blindfolds were put on, the proceedings of the experiment were explained to the participants. At this point they were to allowed to discuss the matter and devise a protocol, i.e., the manner in which they would be going to make their guesses. Subsequently, no communication would be possible?

Can you devise a protocol that will guarantee at least one right guess?

$\endgroup$

marked as duplicate by Jaap Scherphuis, greenturtle3141, Gareth McCaughan Jun 28 at 15:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Of course you're right. I should have checked for dupes before answering. Oops. $\endgroup$ – Gareth McCaughan Jun 28 at 15:22
  • $\begingroup$ It's not easy to find this duplicate. Even with a hats tag, there are just so many variations of hat puzzles that are not quite the same.... $\endgroup$ – Jaap Scherphuis Jun 28 at 15:24
5
$\begingroup$

Each participant

is allocated a number from $0$ to $N-1$. Then participant $k$ predicts his hat-label using the others he sees plus the assumption that the sum of all the hat-labels is $k$ (mod $N$). One of them must be right.

To be more explicit:

participant $k$ predicts that his hat-label is $k$ minus the sum of all the other labels, mod $N$. If the actual sum of all the labels is $r$, then participant $r$ will predict correctly.

$\endgroup$
  • $\begingroup$ oh wow, I never understood the solution to this, so this is a great explanation. $\endgroup$ – greenturtle3141 Jun 28 at 15:23
  • 2
    $\begingroup$ Yeah, the answers to the question this is a dupe of are ... needlessly laborious. $\endgroup$ – Gareth McCaughan Jun 28 at 15:23
  • $\begingroup$ I didn't understand, each participant guesses that his number (k + the sum he see) mod N? Suppose 3 people with the numbers 1, 2, 1. and the k is 0, 1, 2. the first person say 0 + 3 mod 3 = 0 is incorrect, the second person say 1 + 2 mod 3 = 0 is incorrect, the third person say 2 + 3 mod 3 = 2 is incorrect. $\endgroup$ – user61165 Jun 28 at 16:23
  • $\begingroup$ Participant 0 guesses his number k0 so that (k0 + sum of other numbers) mod N is 0. Participant 1 guesses his number k1 so that (k1 + sum of other numbers) mod N is 1. Etc. If the actual sum of all the numbers mod N is r, then participant r guesses his number correctly. $\endgroup$ – Gareth McCaughan Jun 28 at 16:33
  • $\begingroup$ I wonder if this is worth merging ... the prior question's answers are indeed lengthy and easy to get lost in. $\endgroup$ – Rubio Jul 2 at 1:26

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