# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Trojan Horse
Daedalian Member

 Posted: Fri Oct 28, 2011 3:50 am    Post subject: 1 Here's a variation of the "what color of hat is on my head?" puzzle. I came up with this variation on my own, though I'm sure others have thought of it independently. First, here's the original puzzle, for those that are not familiar with it: Five people are playing a game. They are seated in a circle, and a hat (either red or blue) is placed on each person's head. Each person can see the colors of all the other hats, but not his own. Each person must guess the color of hat on his own head. If everyone guesses correctly, the group wins the game; if even one guess is wrong, the group loses the game. The group is allowed to strategize together before the game begins. But once the hats are in place, they are not allowed to communicate with each other in any way. What strategy gives them the best chance to win? Answer: Everyone should make their guess under the assumption that the total number of blue hats is even. For example, if someone sees three blue hats and one red hat, he should guess that his hat is blue, so as to make the total number of blues even. The group will win when the total number of blue hats IS even, which will happen 50% of the time. And since each individual guess always has a 50% chance of being right, there's no way the team can do any better. 50% is the best they can do. Of course, they could instead all guess that the total number of blue hats is odd. It makes no difference. Now, here's the variation: let's say that all five people are one-eyed. Each only has his left eye. As a result, each person cannot see the hat on their immediate right; each person can only see the other three hats. As before, the players can strategize in advance. But once the hats are in place, they can't communicate with each other, and they can't turn their heads to see the person on their right. What is their best strategy now?
Zag
Tired of his old title

 Posted: Fri Oct 28, 2011 3:42 pm    Post subject: 2 I assume they have to make their guesses simultaneously? That is, none of them get to hear the guesses of the others before making their own guess, right?
Trojan Horse
Daedalian Member

 Posted: Fri Oct 28, 2011 3:59 pm    Post subject: 3 Correct.
Thok*
Guest

Posted: Sun Oct 30, 2011 4:19 am    Post subject: 4

 Trojan Horse wrote: What is their best strategy now?

I get a 6/32 strategy as follows

Guess whatever makes the position either looks like RRRBB up to rotation or BBBBB up to rotation. I'm not convinced that is best.
ralphmerridew
Daedalian Member

 Posted: Sun Oct 30, 2011 1:50 pm    Post subject: 5 Computer search found 8/32: Assume the pattern is one of rrrrr, rrBrB, rBrBr, rBBBB, BrrBB, BrBBr, BBrrB, BBBrr
ralphmerridew
Daedalian Member

 Posted: Sun Oct 30, 2011 2:28 pm    Post subject: 6 Trying for other numbers hats reveals that for 2,3,4,6 people, maximum win is 1/4; a search of 7 hats found a 1/4 solution, but hasn't run to exhaustion yet. There ought to be a simple proof that 1/4 is an upper bound for 2 or more hats.
ralphmerridew
Daedalian Member

 Posted: Sun Oct 30, 2011 3:16 pm    Post subject: 7 And there is: Select two adjacent people, Alice and Bob. Define two hatsets as equivalent if all hats, other than those worn by Alice and Bob, are the same. There are 2^n / 4 equivalence classes. It is possible for them to win in at most one hatset in any equivalence class; therefore, they can win at most (2^n/4) / (2^n) = 1/4.
Trojan Horse
Daedalian Member

 Posted: Sun Oct 30, 2011 3:42 pm    Post subject: 8 Congrats, ralphmerridew. That does it. I'm currently trying to generalize this problem: I'm looking at what happens when there are n colors of hats, and each person can see all but m of the hats (their own, and the m-1 to their right). It's easy to get an upper bound for how well the team can do; it's [1/(n^m)], by a similar reasoning to what you just gave. But I don't yet know that this bound can always be achieved.
ralphmerridew
Daedalian Member

 Posted: Mon Oct 31, 2011 1:53 am    Post subject: 9 The theoretical maximum seems to always be achievable, and with a linear code. Number hats 0, 1, ... (NCOLORS - 1). Definition: A "hat-case" is an ordered list of NPEOPLE values from 0 to NCOLORS-1. Definition: For two hat-cases A and B, define C := A (+) B as the hatcase such that C[i] = (A[i] + B[i]) mod NCOLORS. Definition: A set S of hat-cases is a linear code iff: 1) The hat-case with all zeros is in S. 2) For any two hat-cases A and B (not necessarily distinct) in S, A (+) B is also in S. For any number of colors, the linear code generated by (1,-1,0,...), (0,1,-1,0,...), (0,0,1,-1,0,...) ... (0,...,1,-1) is an optimal solution for m=1. For any number of colors, the linear code generated by (1,0,1,0,1) and (0,1,1,1,1) is an optimal solution for 5 people, m = 3. (1,0,1,0,0), (0,1,0,1,0), (0,0,1,1,1) generates an optimal solution for 5 people, m=2. If there is an optimal solution for n colors, p people, m hidden hats, then there's an optimal solution for n colors, p*d people, m*d hidden hats. (Each person considers only himself, and the people d,2d,3d, ...(p-1)d to his left; split the problem into d disjoint subproblems.). For p odd, m=2, (1,0,1,0,0,...), (0,1,0,1,0,...), (0,0,1,0,1,0,...), ... (0,..0,1,0,1,0), (0,...,0,1,1,1) generates a solution.
Zag
Tired of his old title

Posted: Mon Oct 31, 2011 2:18 pm    Post subject: 10

 ralphmerridew wrote: Computer search found 8/32: Assume the pattern is one of rrrrr, rrBrB, rBrBr, rBBBB, BrrBB, BrBBr, BBrrB, BBBrr

If I see BrB, how do I choose between assuming I'm last in rBrBr, or fourth in BrBBr?
Edit: I'm guessing that your patterns are fixed, since some of them are rotations of each other, anyway.
Nsof
Daedalian Member

 Posted: Sun Nov 20, 2011 10:24 pm    Post subject: 11 Call the original puzzle "2 hat colors where each person can see all but own hat" - P(2,1). Generally, P(n,m) where n is the number of hat colors and m is the number of hats not seen. The original post asked for P(2,2) Using the same strategy as suggested in the original post its relatively easy to show 1. P(n,1) = 1/n. Im having trouble with this* 2. P(2,m) = P(2^m,1) but then this would follow 3. P(n,m)=(n^m,1)=1/n^m *Strong intuition/seems right/makes sense/yada yada reduction maybe?
ralphmerridew
Daedalian Member

 Posted: Mon Nov 21, 2011 2:19 am    Post subject: 12 This seems to work: For p people, each able to see m hats, and unable to see p-m hats: Let Q = (floor (p/m))*m. Define b(x,y) for 0 <= x < p, 0 <= y < m such that: b(x,y) := 1 if x < Q and x == y (mod p) 0 if x < Q and x != y (mod p) ... and the parts when x >= Q, I can't find a general rule that works, but I've been able to find one for every combination of p, m that I've tried. Consider the linear code generated by { (b(0,y), b(1,y), ..., b(p-1,y)) | 0 <= y < m }. In advance, choose one person as the root. Each person assumes that the hatset is in the code.
Deception
Daedalian Member

 Posted: Mon Nov 21, 2011 3:34 am    Post subject: 13 Answer: They can strategize before the game, correct? Each person holds up fingers denoting the color of the hat the person to their immediate left is wearing in your left hand, and in your right hand the color of hat that the person two spaces to your left is wearing. 1= red 2= blue Seems easy enough, are you guys over complicating this or am I cheating?
grz*
Guest

 Posted: Mon Nov 21, 2011 7:08 pm    Post subject: 14 I think you're breaking the clause that they may not communicate *in any way.* If they are sharing information then they are communicating, by definition.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAnonymousDeceptionNsofralphmerridewTrojan HorseZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum