4

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?

gabbo1092
  • 6,000
  • 1
  • 15
  • 45
user61165
  • 41
  • 1

1 Answers1

5

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.

Gareth McCaughan
  • 119,120
  • 7
  • 313
  • 454
  • oh wow, I never understood the solution to this, so this is a great explanation. – greenturtle3141 Jun 28 '19 at 15:23
  • 2
    Yeah, the answers to the question this is a dupe of are ... needlessly laborious. – Gareth McCaughan Jun 28 '19 at 15:23
  • 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. – user61165 Jun 28 '19 at 16:23
  • 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. – Gareth McCaughan Jun 28 '19 at 16:33
  • I wonder if this is worth merging ... the prior question's answers are indeed lengthy and easy to get lost in. – Rubio Jul 02 '19 at 01:26