Yet Another Puzzle with Hats

There is a great variety of puzzles where wise people sit in a circle seeing each other's hat but not their own. The task before each of them is to guess his own kind of hat.

The puzzle below has been communicated to me by Anany Levitin, an old classmate of mine. Later on I came across an article A Dozen Hat Problems by Ezra Brown and James Tanton (Math Horizons, v 16, nr 4, April 2009, pp. 22-25) in which is was problem #2, with #1 as a simplified, warm-up version. The problem is about hats and guessing, but does not assume equal wisdom of the participants nor does it require each of them to come up with the correct answer. Just one of them needs to hit on the right response. The puzzle is as follows:

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 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?

Solution

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?

Solution

Consider one of the participants. The fellow sees the numbers on all others' hats, but his own. Let his number be x and denote the sum of the numbers on all N hats as S. Summing up the numbers visible to him, the fellow can find S - x. This is probably the only useful information he may be exploiting. (A more honest way to put it is to admit that I can't see how it may be possible to make use of individual numbers.)

Here's a solution that makes use of the arithmetic modulo N. During the preliminary discussion each of the participants was assigned a unique number from the set of the residues {0, 1, ..., N-1}. Say, a is the number assigned to a generic participant. It was agreed that, when the time comes, each would write a residue (modulo N) y such that

S - x + y = a (mod N).

The reasoning for this behavior is simple enough. The unknown S is equivalent to some s from the set {0, 1, ..., N-1}. The above can be written then as

s - x + y = a (mod N).

Since all a's assigned were different, one of them is necessarily equal to s. For this participant, the latter equation becomes

s - x + y = s (mod N),

or,

x - y = 0 (mod N).

Since both x and y are residues modulo N, this implies their equality: x = y, meaning that this fellow will actually correctly guess his number.

71924319