EPTi was skeptical about this answer, i messed around with some calculations in excel, i can find counter examples to this and thus this answer does not solve the problem 100%
prisoner 0 1 2 3 4 5 6
his color 6 6 6 1 1 1 1
written color 2 2 2 3 3 3 3
Math Puzzle - 7 Hats - Page 6
| Blogs > Slithe |
|
saltywet
Hong Kong1316 Posts
i was skeptical about this answer, i messed around with some calculations in excel, i can find counter examples to this and thus this answer does not solve the problem 100% prisoner 0 1 2 3 4 5 6 his color 6 6 6 1 1 1 1 written color 2 2 2 3 3 3 3 | ||
|
BottleAbuser
Korea (South)1888 Posts
On September 10 2010 07:07 Slithe wrote: Let me try and explain Karlsberg's solution a little bit + Show Spoiler [solution] + We assign each color a number from 0-6 Now we can say that the prisoners are essentially getting a number, c0,c1,c2,c3,c4,c5,c6. S = (c0 + c1 + c2 + c3 + c4 + c5 + c6) modulo 7 S has seven possible values, 0-6 At this point, what each prisoner is doing is trying to guess what S is, and solving for their own number to match S. Prisoner 0 assumes S = 0, and solves the equation c0 = S - (c1+c2+c3+c4+c5+c6) Prisoner 1 assumes S = 1, and solves the equation c1 = S - (c0+c2+c3+c4+c5+c6) and so on.. At least one of the 7 prisoners will assume the correct S value. That prisoner will be able to guess the correct number for their own hat. I am so embarrassed. | ||
|
Nytefish
United Kingdom4282 Posts
On September 10 2010 07:07 Slithe wrote: Let me try and explain Karlsberg's solution a little bit + Show Spoiler [solution] + We assign each color a number from 0-6 Now we can say that the prisoners are essentially getting a number, c0,c1,c2,c3,c4,c5,c6. S = (c0 + c1 + c2 + c3 + c4 + c5 + c6) modulo 7 S has seven possible values, 0-6 At this point, what each prisoner is doing is trying to guess what S is, and solving for their own number to match S. Prisoner 0 assumes S = 0, and solves the equation c0 = S - (c1+c2+c3+c4+c5+c6) Prisoner 1 assumes S = 1, and solves the equation c1 = S - (c0+c2+c3+c4+c5+c6) and so on.. At least one of the 7 prisoners will assume the correct S value. That prisoner will be able to guess the correct number for their own hat. Ah I read Karlsberg's solution and was typing up the explanation but I thought I'd refresh to see if someone else had mentioned it already.  I'm surprised so many people thought there was a silly gimmick to this problem despite it being called a math puzzle. | ||
|
Lark
United States24 Posts
On September 10 2010 07:12 saltywet wrote: i was skeptical about this answer, i messed around with some calculations in excel, i can find counter examples to this and thus this answer does not solve the problem 100% prisoner 0 1 2 3 4 5 6 his color 6 6 6 1 1 1 1 written color 2 2 2 3 3 3 3 I think you forgot to add the prisoner numbers, since prisoners 0,1, and 2 all see the same sum but are guessing the same number... | ||
|
BottleAbuser
Korea (South)1888 Posts
| ||
|
Slithe
United States985 Posts
On September 10 2010 07:12 saltywet wrote: i was skeptical about this answer, i messed around with some calculations in excel, i can find counter examples to this and thus this answer does not solve the problem 100% prisoner 0 1 2 3 4 5 6 his color 6 6 6 1 1 1 1 written color 2 2 2 3 3 3 3 prisoner 0 1 2 3 4 5 6 his color 6 6 6 1 1 1 1 sum of others 2 2 2 0 0 0 0 written color 5 6 0 3 4 5 6 prisoner 1 gets it right. | ||
|
Logo
United States7542 Posts
Each guessing strategy has to win for square root of n^n unique combinations where n is the # of people (so for 2 each person has a strategy that wins squareroot of 2*2 BB WW is one person BW WB is another). For 3 people each strategy needs to win for 9 unique cases. Edit looks like someone got the answer vs my explanation of what the answer requires. | ||
|
Impervious
Canada4217 Posts
| ||
|
jalstar
United States8198 Posts
Possible red, orange, yellow, green, blue, indigo, violet Actual red, red, red, yellow, blue, indigo, indigo Red = 0, Orange = 1, Yellow = 2, Green = 3, Blue = 4, Indigo = 5, Violet = 6 Prisoner 0 (red) Sees red, red, yellow, blue, indigo, indigo for a sum of 16. Adds his own number, 0. 16%7 = 2. Guesses yellow. Prisoner 1 (red) Sees red, red, yellow, blue, indigo, indigo for a sum of 16. Adds his own number, 1. 17%7 = 3. Guesses green. Prisoner 2 (red) Sees red, red, yellow, blue, indigo, indigo for a sum of 16. Adds his own number, 2. 18%7 = 4. Guesses blue. Prisoner 3 (yellow) Sees red, red, red, blue, indigo, indigo for a sum of 14. Adds his own number, 3. 17%7 = 3. Guesses green. Prisoner 4 (blue) Sees red, red, red, yellow, indigo, indigo for a sum of 12. Adds his own number, 4. 16%7 = 2. Guesses yellow. Prisoner 5 (indigo) Sees red, red, red, yellow, blue, indigo for a sum of 11. Adds his own number, 5. 16%7 = 2. Guesses yellow. Prisoner 6 (indigo) Sees red, red, red, yellow, blue, indigo for a sum of 11. Adds his own number, 6. 17%7 = 2. Guesses green. All prisoners die. Let me know if there's a problem with my proof by contradiction, but I think Karlsberg's solution doesn't work. + Show Spoiler [Non-mathematical answer] + This doesn't break any rules in the OP. Two prisoners agree beforehand to write each other's names on their pieces of paper. They also write the color of the hat that the other person is wearing. Bam, foolproof answer. | ||
|
saltywet
Hong Kong1316 Posts
On September 10 2010 07:16 Slithe wrote: prisoner 0 1 2 3 4 5 6 his color 6 6 6 1 1 1 1 sum of others 2 2 2 0 0 0 0 written color 5 6 0 3 4 5 6 prisoner 1 gets it right. i got some mistake, written color i actually get 2 3 4 3 4 5 6 using [(number* of prisoner) + (color of other prisoners)]%7 how did you get 5 6 0 for prisoner 0 1 2 | ||
|
The_Pacifist
United States540 Posts
But now I feel stupid for having to google it.  | ||
|
gondolin
France332 Posts
On September 10 2010 07:14 Lark wrote: I think you forgot to add the prisoner numbers, since prisoners 0,1, and 2 all see the same sum but are guessing the same number... Even so it does not work: consider 0 1 2 3 4 5 6 0 2 2 3 4 5 6 1 1 1 1 1 1 1 | ||
|
jalstar
United States8198 Posts
Prisoner 0 1 2 3 4 5 6 Simpler form. | ||
|
Slithe
United States985 Posts
On September 10 2010 07:25 jalstar wrote: Red = 0, Orange = 1, Yellow = 2, Green = 3, Blue = 4, Indigo = 5, Violet = 6 Prisoner 0 (red) Sees red, red, yellow, blue, indigo, indigo for a sum of 16. Adds his own number, 0. 16%7 = 2. Guesses yellow. Prisoner 1 (red) Sees red, red, yellow, blue, indigo, indigo for a sum of 16. Adds his own number, 1. 17%7 = 3. Guesses green. Prisoner 2 (red) Sees red, red, yellow, blue, indigo, indigo for a sum of 16. Adds his own number, 2. 18%7 = 4. Guesses blue. Prisoner 3 (yellow) Sees red, red, red, blue, indigo, indigo for a sum of 14. Adds his own number, 3. 17%7 = 3. Guesses green. Prisoner 4 (blue) Sees red, red, red, yellow, indigo, indigo for a sum of 12. Adds his own number, 4. 16%7 = 2. Guesses yellow. Prisoner 5 (indigo) Sees red, red, red, yellow, blue, indigo for a sum of 11. Adds his own number, 5. 16%7 = 2. Guesses yellow. Prisoner 6 (indigo) Sees red, red, red, yellow, blue, indigo for a sum of 11. Adds his own number, 6. 17%7 = 2. Guesses green. All prisoners die. Let me know if there's a problem with my proof by contradiction, but I think Karlsberg's solution doesn't work. + Show Spoiler [Non-mathematical answer] + This doesn't break any rules in the OP. Two prisoners agree beforehand to write each other's names on their pieces of paper. They also write the color of the hat that the other person is wearing. Bam, foolproof answer. You're right, Karlsberg actually didn't give quite the right solution, but it looked similar to the right answer so I got tricked. Consult my spoiler for the correct solution. Instead of doing sum + own_number = color, you do own_number - sum = color. In your example, I believe prisoner 2 has 2 - 16 = 0 % 7, and guesses red correctly. | ||
|
saltywet
Hong Kong1316 Posts
On September 10 2010 07:30 gondolin wrote: Even so it does not work: consider 0 1 2 3 4 5 6 0 2 2 3 4 5 6 1 1 1 1 1 1 1 prisoner 1 would actually be 0, but that still does not change the point  | ||
|
djcube
United States985 Posts
| ||
|
LeoTheLion
China958 Posts
On September 10 2010 07:25 jalstar wrote: Red = 0, Orange = 1, Yellow = 2, Green = 3, Blue = 4, Indigo = 5, Violet = 6 Prisoner 0 (red) Sees red, red, yellow, blue, indigo, indigo for a sum of 16. Adds his own number, 0. 16%7 = 2. Guesses yellow. Prisoner 1 (red) Sees red, red, yellow, blue, indigo, indigo for a sum of 16. Adds his own number, 1. 17%7 = 3. Guesses green. Prisoner 2 (red) Sees red, red, yellow, blue, indigo, indigo for a sum of 16. Adds his own number, 2. 18%7 = 4. Guesses blue. Prisoner 3 (yellow) Sees red, red, red, blue, indigo, indigo for a sum of 14. Adds his own number, 3. 17%7 = 3. Guesses green. Prisoner 4 (blue) Sees red, red, red, yellow, indigo, indigo for a sum of 12. Adds his own number, 4. 16%7 = 2. Guesses yellow. Prisoner 5 (indigo) Sees red, red, red, yellow, blue, indigo for a sum of 11. Adds his own number, 5. 16%7 = 2. Guesses yellow. Prisoner 6 (indigo) Sees red, red, red, yellow, blue, indigo for a sum of 11. Adds his own number, 6. 17%7 = 2. Guesses green. All prisoners die. Let me know if there's a problem with my proof by contradiction, but I think Karlsberg's solution doesn't work. + Show Spoiler [Non-mathematical answer] + This doesn't break any rules in the OP. Two prisoners agree beforehand to write each other's names on their pieces of paper. They also write the color of the hat that the other person is wearing. Bam, foolproof answer. you subtract the sum from the prisoner's own number, not add. so we have 0-16 = 5 mod 7 1-16 = 6 2-16 = 0 3-14 = 3 4-12 = 6 5-10 = 2 6-10 = 1 prisoner 2 gets it right | ||
|
Glull
Germany404 Posts
| ||
|
Slithe
United States985 Posts
On September 10 2010 07:28 saltywet wrote: i got some mistake, written color i actually get 2 3 4 3 4 5 6 using [(number* of prisoner) + (color of other prisoners)]%7 how did you get 5 6 0 for prisoner 0 1 2 Karlsberg's solution was slightly wrong, look at my solution for the way to do it. | ||
|
Logo
United States7542 Posts
On September 10 2010 07:33 Glull wrote: this solution doesnt work because it relies on the prisoners communicating their own number, which is not possible with the scenario in the opening post. The problem clearly states the prisoners know the colors and they can't communicate after being seating. It makes no mention of before. | ||
| ||
