EPTAlso yes the amount of people trying to solve this blatant maths puzzle via communication was lol.
Math Puzzle - 7 Hats - Page 7
| Blogs > Slithe |
|
Muff2n
United Kingdom250 Posts
Also yes the amount of people trying to solve this blatant maths puzzle via communication was lol. | ||
|
Slithe
United States985 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 prisoners designate a number to each guy beforehand. They are free to communicate a strategy before sitting down. @Muff2n, I posted the solution in the opening post. | ||
|
gondolin
France332 Posts
On September 10 2010 07:32 saltywet wrote: prisoner 1 would actually be 0, but that still does not change the point  Oh yeah thanks, I suck at calculus  I started from 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 0 0 0 0 0 0 then add 1 to the color of number 1, or add two to the color of number 2, ... The same counter example work if you substract the number of the person, you start with 0 1 2 3 4 5 6 0 -1 -2 -3 -4 -5 -6 0 0 0 0 0 0 0 and you substract 1 to the colors of number 1, or two to the color of number 2, ... Edit: Howewer it works indeed if we substract the counted color: the person i announce i-(S-c_i), and he wins when i-(S-c_i)=c_i, so when i=S. | ||
|
Happy.fairytail
United States327 Posts
For example, Guy1 sees 11 and if he choses 1, then 111 is taken care of, but Guy1 is no longer able to test for 211 and 311. However, Guy2 will be able to test for 211 when he sees 21 and chooses 1 and Guy3 will be able to test for 311 when he sees 31 and chooses 1. However, then Guy2 will be unable to test for 221 and 231, and Guy3 is unable to test for 312 and 313. But as long as you're able to keep going and make sure the other 2 guys can test for the combinations you can't test, you're ok -- and there is ONE solution, given like I said, that will cover 27 combinations, by using 3 people who each will see 9 scenarios. And if you extend that to 7 hats, there are 823,543 combinations, 117,649 scenarios and 7 guys. Haha...I wonder if there's a way to solve this problem using matrices rather than straight up mod equations... | ||
|
Slithe
United States985 Posts
On September 10 2010 07:43 Happy.fairytail wrote: I guess I'm not a mathematician after all :D but here's my ENFP intuitive way of thinking about it... in a 3 hat problem, there are 27 possible combinations. Each person will see 9 possible scenarios. If you find a way such that each person gives a different answer for each of the 27 possible combinations using the 9 scenioars they see, you can cover all your bases. For example, Guy1 sees 11 and if he choses 1, then 111 is taken care of, but Guy1 is no longer able to test for 211 and 311. However, Guy2 will be able to test for 211 when he sees 21 and chooses 1 and Guy3 will be able to test for 311 when he sees 31 and chooses 1. However, then Guy2 will be unable to test for 221 and 231, and Guy3 is unable to test for 312 and 313. But as long as you're able to keep going and make sure the other 2 guys can test for the combinations you can't test, you're ok -- and there is ONE solution, given like I said, that will cover 27 combinations, by using 3 people who each will see 9 scenarios. And if you extend that to 7 hats, there are 823,543 combinations, 117,649 scenarios and 7 guys. Haha...I wonder if there's a way to solve this problem using matrices rather than straight up mod equations... Your way of thinking about it is good. Now all you have to do is find a proper mapping from the combinations to the people's guesses | ||
|
saltywet
Hong Kong1316 Posts
On September 10 2010 07:36 Slithe wrote: Karlsberg's solution was slightly wrong, look at my solution for the way to do it. i still dont know how you got 5 6 0 say for prison 0, color of other prisoners = 6+6+4*1 = 16, 0 -16 = 16, mod7 = 2, so how did you get 5? anyways i used your solution for another problem [(number of prison)-(color of other prisoners)]%7 prisoner 0 1 2 3 4 5 6 his color 6 6 6 3 3 2 3 written color 2 1 0 2 1 1 6 solution check: prisoner 0 0-(6+6+3+3+2+3) = 23, mod7 = 2 prisoner 1 1-(6+6+3+3+2+3) = 22, mod7 = 1 prisoner 2 2-(6+6+3+3+2+3) = 21, mod7 = 0 prisoner 3 3-(6+6+6+3+2+3) = 23, mod7 = 2 prisoner 4 4-(6+6+6+3+2+3) = 22, mod7 = 1 prisoner 5 5-(6+6+6+3+3+3) = 22, mod7 = 1 prisoner 6 6-(6+6+6+3+2+3) = 20, mod7 = 6 | ||
|
BottleAbuser
Korea (South)1888 Posts
+ Show Spoiler + We start with the fact that the summation of the values of the hats modulo 7 is a number between 0 and 6, inclusive, and it doesn't change once the hats have been assigned. That is, [hat1 + hat2 + hat3 + hat4 + hat5 + hat6 + hat7] % 7 = C, for some number C that can't change. For each prisoner, there is one unknown hat (his own). There is also the unknown value C. If he guesses a value for C, then he can solve for his own hat value. Since there are 7 possible values for C, each prisoner agrees to choose a different value to guess for C. Then, exactly 1 prisoner will choose the correct value (the other 6 will choose the wrong values). He will then proceed to guess his own hat value correctly. Note that this won't work if you have fewer prisoners than hat colors. | ||
|
silveryms
United States23 Posts
Let c_i denote the color (0-6) for player i. Let C denote the sum of all c_i Now, we know that x = C (mod 7) for some value of x between 0 and 6. This is a property of mods. Now let's say each player i picks a color p_i = i - (C - c_i) (mod 7). (C - c_i) is observable by looking at the sum of all the other hats. So p_i = i - C + c_i (mod 7). For player x though, we know that x = C (mod 7). So if we add these two mod relations together (another property of mods) we get: p_x + x = x - C + c_x + C (mod 7). Therefore, p_x + x = c_x + x (mod 7) And since x is less than 7, p_x = c_x. So player x will pick his number! | ||
|
Slithe
United States985 Posts
On September 10 2010 07:48 saltywet wrote: i still dont know how you got 5 6 0 say for prison 0, color of other prisoners = 6+6+4*1 = 16, 0 -16 = 16, mod7 = 2, so how did you get 5? anyways i used your solution for another problem [(number of prison)-(color of other prisoners)]%7 prisoner 0 1 2 3 4 5 6 his color 6 6 6 3 3 2 3 written color 2 1 0 2 1 1 6 solution check: prisoner 0 0-(6+6+3+3+2+3) = 23, mod7 = 2 prisoner 1 1-(6+6+3+3+2+3) = 22, mod7 = 1 prisoner 2 2-(6+6+3+3+2+3) = 21, mod7 = 0 prisoner 3 3-(6+6+6+3+2+3) = 23, mod7 = 2 prisoner 4 4-(6+6+6+3+2+3) = 22, mod7 = 1 prisoner 5 5-(6+6+6+3+3+3) = 22, mod7 = 1 prisoner 6 6-(6+6+6+3+2+3) = 20, mod7 = 6 0-16 = -16 = 5 mod 7 equivalently, 21 = 0 mod 7, 21-16 = 5 mod 7 For your new solution, I'll just arithmetic check your first prisoner. 0-(6+6+3+3+2+3) = -23, mod7 = 5 | ||
tofucake
Hyrule19192 Posts
On September 10 2010 07:48 saltywet wrote: say for prison 0, color of other prisoners = 6+6+4*1 = 16, 0 -16 = 16, mod7 = 2, so how did you get 5? I still don't know how you got -16 = 16 But his logic, while wrong, is sound. -2 is outside 0..7, so add 7. -2+7=5 But that's not how modulo works. | ||
|
Phant
United States737 Posts
On September 10 2010 07:55 Slithe wrote: 0-16 = -16 = 5 mod 7 equivalently, 21 = 0 mod 7, 21-16 = 5 mod 7 For your new solution, I'll just arithmetic check your first prisoner. 0-(6+6+3+3+2+3) = -23, mod7 = 5 you have to get a positive integer for the remainder. -16 divided by 7 could be -2 with a remainder -2, but in order to make it positive, it would be -3 remainder 5. 7*-3 = -21 +5 = 16. | ||
|
Slithe
United States985 Posts
Also, -21 +5 = -16, not 16. Am I getting trolled here? | ||
|
BottleAbuser
Korea (South)1888 Posts
phant, mod works like this: If you have x % y = z, then that means y * c + z = x, for some integer c. So, if we are looking at -16 % 7 = 5, let's verify that it works. 7 * -3 + 5 = -21 + 5 = -16, so yes it works. (we can use -3 because -3 is an integer.) | ||
|
Phant
United States737 Posts
On September 10 2010 08:20 BottleAbuser wrote: lulz. phant, mod works like this: If you have x % y = z, then that means y * c + z = x, for some integer c. So, if we are looking at -16 % 7 = 5, let's verify that it works. 7 * -3 + 5 = -21 + 5 = -16, so yes it works. (we can use -3 because -3 is an integer.) which...is exactly what i was saying. the mod function finds the remainder, of course you can define the remainder in many ways, but in most cases like this you want it to be positive. edit: oh I see, I forgot to throw a negative sign on 16, typo on my part. 2nd edit, I also just noticed I quoted the wrong post, wow i am not on top of things today, I was responding to the person who you quoted, Slithe | ||
|
Muff2n
United Kingdom250 Posts
Now I just need to become a little more happy with mod (first time I saw the % I thought the guy must have miss-pressed / or ^ or something lol) | ||
|
garbanzo
United States4046 Posts
Since this is a group, the result is an element of the group. So each person just has to account for one element of the group. This way you're guaranteed that someone is right. It doesn't work if there are more hat colors than prisoners because you can never account for every element. The result might map to a different element that someone isn't guessing. Obviously this will still work if there are more prisoners than colors because you can just make up colors to fill in the empty space. But is there a different solution that would maximize the number of correct guesses if there are less hat colors? | ||
| ||
