# Numbered hats puzzle



## shelley (Oct 1, 2010)

Rather than hijack an unrelated thread, I should put this in a new one.



> N people sit in a circle. There are hats with numbers on them, and each hat's number is an integer from 1 to N inclusive. Someone goes around and puts these hats on everyone's head. The number on each hat is randomly chosen, so that not all N numbers may be represented, and people may be wearing hats with the same number.
> 
> Naturally, each person in the circle can see everyone else's hat number but not their own, and they have to try to guess the number on the hat they're wearing. Once the game begins they are not allowed to communicate, and everyone must make their guess at the same time. What strategy will ensure that exactly one person will guess his hat number correctly?



Hint: here are some easier puzzles that may lead you to the solution.



> 10 gnomes stand in a single file line so that each gnome can see all the gnomes lined up in front of him but not the ones behind him. Randomly chosen black and white hats are placed on each gnome's head. Starting from the last gnome in line (the one who can see all the others), each one guesses which color hat he is wearing. Aside from hearing the answers given before them, no other communication is allowed among the gnomes. What strategy will maximize the number of correct guesses?





> N people sit in a circle, as in the original puzzle. Everyone wears a randomly chosen black or white hat. What strategy will guarantee either *everyone guesses correctly* or *everyone guesses incorrectly*?





> Same conditions as previous. What strategy will guarantee exactly half of the group will guess correctly and the other half will guess incorrectly?


----------



## Litz (Oct 1, 2010)

shelley said:


> N people sit in a circle. There are hats with numbers on them, and each hat's number is an integer from 1 to N inclusive. Someone goes around and puts these hats on everyone's head. The number on each hat is randomly chosen, so that not all N numbers may be represented, and people may be wearing hats with the same number.
> 
> Naturally, each person in the circle can see everyone else's hat number but not their own, and they have to try to guess the number on the hat they're wearing. Once the game begins they are not allowed to communicate, and everyone must make their guess at the same time. What strategy will ensure that exactly one person will guess his hat number correctly?





Spoiler



I didn't think too much about it and don't even know if something like this is allowed, but the way I'd do it (assuming I knew everyone else), would be to pick a player to win (this would be labeled N, for instance). Then every other player would have a "hidden" number too, which would be N-position relative to the "winner". This means the one on the right of the "winner" could be N-1, and the one to his left would be 1. Then everyone would see his hat number, and if they were his number, they would keep looking. If not, they'd look away. This way, either 1 player will be looking at the "winner" (in which case the "winner" says that players' "hidden" number), or no one will be looking at the "winner", meaning his number is N. Sorry if this is too confusing but it's hard to explain by text..


----------



## AngeL (Oct 1, 2010)

shelley said:


> Stop calling it Einstein's problem, Einstein has nothing to do with it. It's not even like this is a really hard puzzle either. It's basically Sudoku.
> 
> You want a puzzle? Try this one on for size:
> 
> ...


 

How much preparation does the group have beforehand? It seems like if they can plan it out, they could just all assign themselves numbers from 1 to N, so each person guesses a different number. Then one person would have every number covered.


----------



## shelley (Oct 1, 2010)

AngeL said:


> How much preparation does the group have beforehand? It seems like if they can plan it out, they could just all assign themselves numbers from 1 to N, so each person guesses a different number. Then one person would have every number covered.



Let's just say they get the night before to plan out their strategy.
How does your solution ensure that exactly one person (or anyone for that matter) guesses his number correctly? Isn't it basically blind guessing?



Litz said:


> Spoiler
> 
> 
> 
> I didn't think too much about it and don't even know if something like this is allowed, but the way I'd do it (assuming I knew everyone else), would be to pick a player to win (this would be labeled N, for instance). Then every other player would have a "hidden" number too, which would be N-position relative to the "winner". This means the one on the right of the "winner" could be N-1, and the one to his left would be 1. Then everyone would see his hat number, and if they were his number, they would keep looking. If not, they'd look away. This way, either 1 player will be looking at the "winner" (in which case the "winner" says that players' "hidden" number), or no one will be looking at the "winner", meaning his number is N. Sorry if this is too confusing but it's hard to explain by text..


 
Sorry, that counts as communication. You can't use any other information aside from the hat numbers that you can see, so you can't use whether someone is looking at you or not. Also, everyone has to submit a guess at the same time. If in addition to the designated "winner" one of the "non-winners" happens to guess his number by chance, everyone loses (the objective is to have exactly one person guess correctly).


----------



## Litz (Oct 1, 2010)

shelley said:


> Sorry, that counts as communication. You can't use any other information aside from the hat numbers that you can see, so you can't use whether someone is looking at you or not. Also, everyone has to submit a guess at the same time. If in addition to the designated "winner" one of the "non-winners" happens to guess his number by chance, everyone loses (the objective is to have exactly one person guess correctly).


Ah ok. That wouldn't be a problem though since everyone could know at least a number they weren't (the group of persons could make a system where every N looks at N-1 if N-1 actual number is indeed N-1, and not look elseway, so every person would know which number to pick: his "hidden" number or a random number besides that one).

If this counts as communication it's no good though, and neither are "hidden" numbers. I'll think about it some more


----------



## Erzz (Oct 1, 2010)

Is guessing numbers that aren't possible allowed? Like if hats had 1 through 10, and someone guessed 11.


----------



## Stefan (Oct 1, 2010)

I suggest we call these puzzles A to D and people state before their spoiler which puzzle they're addressing. So that one can read spoilers for problems already solved.

Puzzle B (the 10 gnomes)


Spoiler



Everyone guesses with a high voice if the next has a white hat and low voice if the next has a black hat, so all but the first know and correctly guess their color.

Or: The first gnome guesses "white" iff he sees an odd number of white hats. Then all remaining know and can correctly guess their color based on the initial parity, the number of whites they see in front of them, and the number of whites they hear behind them.


Puzzle C (N black/white hats, make all win or all lose)


Spoiler



Everyone guesses assuming the total number of white hats even. If it really is even, then all are right, otherwise all are wrong.


Puzzle D (N black/white hats, make half win and half lose)


Spoiler



Half guess assuming the total number of white hats is even, half guess assuming it's odd. If it is even, the first half are right, otherwise the second half are right.


Puzzle A


Spoiler



They number themselves persons 1 to N. Then person x guesses its number assuming the total sum equals x modulo N. Whatever the total sum modulo N actually is, exactly one of them assumed it correctly and thus guessed its own number correctly.


I haven't really tried "Einstein's puzzle" yet, though I suspect it's more laborious and less interesting than these here.


----------



## Cyrus C. (Oct 1, 2010)

@Stefan: They have to guess at the same time. I think that counts as communication also, Shelley said you could only use the numbers on the hats to figure it out. However, I have no idea how this is possible without communication such as that.


----------



## Joker (Oct 1, 2010)

Pretty much the same as Stefan's. Didn't read his post before I figured it out first.
EDIT
It said guess at the same time for the first puzzle, not the gnomes.


> Starting from the last gnome in line (the one who can see all the others), each one guesses which color hat he is wearing.


But yeah it might be commun.


----------



## Litz (Oct 1, 2010)

Ok, I think I got it. Let me try to explain:



Spoiler



There's N persons and each person gets a number from 1 to N, which will be 'n'. So one person will be n = 1, the person next to him n = 2, etc.
Let's call the sum of all the hat numbers 'S'. Let's say a persons' hat number is called 'm', and the sum of all the hats that person can see is called 'c'. This way:

S = c + m for every person, so if you knew S, you would know your hat number. The only information you know though is n, c and N.

If every person would guess (n - c) % N + 1, one would get it right: Let's call this one 'w'. So there's a S = w % N + 1.

Assume everything is % N + 1 from here on for simplicity:
n - c = n - (S - m) = n - S + m = n + m - S = n + m - w. So for w, n - c = m.

Sorry for the confusing explanation once again...


----------



## ssvfolder (Apr 4, 2012)

*Final solution.*

I just found out about this site, as I was thinking about this puzzle.
It's all in the modulo, and the number completing to achieve it.
Everybody should give their answer according to the following equation:
(Sn+x)%N=i

Where:
Sn - the sum of all number that a person sees (known)
x - added value in order for the above equation to be correct (Eventually this is the correct number)
N - total amount of people
i - the reminder assigned to each person ( the first one is 0, second is 2, third 3, etc.)


----------

