N people, N hat colors, and a One-Way Glass

This is a variant of this question, reproduced below:

There are $n$ people, who will stand in a circle while a game master places a hat on each of their heads. The hats can each be one of $n$ colors (repeats allowed). Each player can see every hat except their own. They all must then simultaneously guess what color hat they are wearing. As long as at least one person guesses correctly, they win. If they are all wrong, they lose.

They may agree on a strategy beforehand, but may not communicate once the hats are placed. Devise a strategy which guarantees they win.

This is a classic problem. If you haven't heard of it, give it a shot before you move on!

Here is the twist:

To make things harder, the game master places a one-way glass between two of the people, Larry and Harry. This means that Larry can see $n-2$ hats (every one else's hat except Harry's), while all other players can see $n-1$ hats.

With this extra obstacle, can they still win (guarantee at least one person guesses correctly)?

• Are Larry and Harry standing adjacent to each other in the circle? Also are we assuming that it's not a mirror, but more of something that Harry can see through but Larry cannot? – MisterEman22 May 30 '15 at 18:56
• @MisterEman22 You can assume they are adjacent. Use whatever term (mirror, glass, window) to describe the thing between Harry and Larry, the functional phrase is "one-way". – Mike Earnest May 30 '15 at 19:01
• Ok. I was confused about it being a "mirror" which would imply that one of them is able to see their own reflection in the mirror. – MisterEman22 May 30 '15 at 19:03
• Ah, i see, I will edit to clarify – Mike Earnest May 30 '15 at 19:26

There is no strategy that guarantees at least one person guesses correctly.

Suppose each person's hat color is selected independently and uniformly at random. Then the probability than any given person guesses their hat color correctly is $1/n$. There are $n$ people, so the expected number of people who guess their hat color is $1$. This implies:

A strategy guarantees that at least one person guesses correctly if and only if that strategy guarantees that at most one person guesses correctly.

Now, suppose they players have decided on a strategy. Choose a color $C_1$. If Larry sees hat color $C_1$ on everyone except Harry, the strategy will dictate a color for Larry to guess, say $C_2$. If Harry sees hats of color $C_1$ on everyone but Larry and sees hat color $C_2$ on Larry, the strategy will dictate a color for Harry to guess, say $C_3$.

This is a problem, because in the event that everyone but Harry and Larry have hat color $C_1$, Larry has hat color $C_2$, and Harry has hat color $C_3$, then both Larry and Harry will guess correctly. This means the strategy they are using allows for the possibility of two people guessing correctly, so the strategy cannot guarantee that at least one person guesses correctly.

• Wow, that was quick, well done! – Mike Earnest May 30 '15 at 19:38

I would think in a smaller group, say of 3 or 4 people, this wouldn't work, nor would anything else. I am proposing and solution for a larger group of people. I am also assuming there and only a few color hats (ex. Blue,yellow, red, green, and they are not using crimson red pink dark green light green lime green neon yellow et cetera). Each person in a larger setting could guess not necessarily what color they think they have, but the color they see the most of. In a large setting, where the basic hat colors would have multiple recurrences, eventually someone would ex: n3 says blue but n9 sees 4 yellow hats and only 3 blue hats, and that n3 has on a red hat, so he also saw 4 yellow hats, therefore allowing n9 to determine there is another blue hat. He is wearing a blue hat.

Another strategy I have devised would work in a smaller setting, more lateral than statistical. Say 3 people. With a one way glass between 2 and 3 where 2 can see 1 and 3 but 3 can only see 1. Whichever person goes first of either 1 or 3 (it was never determined the order in which the guesses would be made), they will guess the color the other is actually wearing. So if 3 guesses before 1 and he says red, 1 then knows he has a red hat.