|
Hyrule18888 Posts
On September 10 2010 06:54 KarlSberg~ wrote:First I really thought that would be going to be something retarded, but that's actually a very nice problem. I think this is the strategy, even though I have a hard time proving it + Show Spoiler + Assign a number to each color (0..6) Assign a number to each prisoner (0..6) Each prisonner adds the colors he sees on all other guys + his number Sum%7 gives the color the prisoner has to announce In any possible case one (exactly one) prisoner will be right.
And once again, what if the King has a 120 pack of Crayolas? Also, the OP states there could be 2 reds and 1 of 5 other colors.
|
Hyrule18888 Posts
On September 10 2010 06:55 tissue wrote: Dear diary,
Today I lost a goodish amount of faith in the intelligence and reading comprehension of the posters on TL.net. Was it like this before starcraft 2? Quite. SC2 Strategy is the worst forum. Stick to blogs and you should be okay.
|
Let me put this another way.
By definition, if events X and Y are independent, the probability of X doesn't change if Y happens, or Y doesn't happen.
Now, it's obvious that if the prisoners' guesses are independent of each others', then there is absolutely no way to guarantee that they will survive.
So, we must conclude that they are dependent.
However, for this dependency to exist, the guesses must be made BEFORE they are seated at the table, because otherwise the information from one guess cannot be passed to the next prisoner. Then, they have absolutely no clue about the distribution of hats.
It's impossible.
|
On September 10 2010 06:54 KarlSberg~ wrote:First I really thought that would be going to be something retarded, but that's actually a very nice problem. I think this is the strategy, even though I'm having a hard time proving it + Show Spoiler +Assign a number to each color (0..6) Assign a number to each prisoner (0..6) Each prisonner adds the colors he sees on all other guys + his number Sum%7 gives the color the prisoner has to announce In any possible case one (exactly one) prisoner will be right.
ding ding ding, we have an answer.
|
Well you can do it for 2 people / 2 hats as shown earlier.
The key is finding a solution for 3 people / 3 hats, then working that up to 4 people / 4 hats, and I'm fairly sure eventually you'd be able to do 7 people / 7 hats.
I'm lazy to solve 3 people / 3 hats, but that's probably how you'd get to it.
(the key is of course that the king doesn't have a 120 pack of crayolas, it's that there are 7 specific colors in the pool)
|
On September 10 2010 06:56 tofucake wrote:Show nested quote +On September 10 2010 06:54 KarlSberg~ wrote:First I really thought that would be going to be something retarded, but that's actually a very nice problem. I think this is the strategy, even though I have a hard time proving it + Show Spoiler + Assign a number to each color (0..6) Assign a number to each prisoner (0..6) Each prisonner adds the colors he sees on all other guys + his number Sum%7 gives the color the prisoner has to announce In any possible case one (exactly one) prisoner will be right.
And once again, what if the King has a 120 pack of Crayolas? Also, the OP states there could be 2 reds and 1 of 5 other colors. The king has 7 colors as stated in the OP. About the second remark... well yes he could. So what?
|
On September 10 2010 06:56 tofucake wrote:Show nested quote +On September 10 2010 06:54 KarlSberg~ wrote:First I really thought that would be going to be something retarded, but that's actually a very nice problem. I think this is the strategy, even though I have a hard time proving it + Show Spoiler + Assign a number to each color (0..6) Assign a number to each prisoner (0..6) Each prisonner adds the colors he sees on all other guys + his number Sum%7 gives the color the prisoner has to announce In any possible case one (exactly one) prisoner will be right.
And once again, what if the King has a 120 pack of Crayolas? Also, the OP states there could be 2 reds and 1 of 5 other colors.
They know ahead of time what the 7 possible colors are.
|
Hyrule18888 Posts
So I won? Sweet.
This problem actually does seem like a mashup of several problems. All of the "prisoners with hats" problems I've heard were limited to a set of 1 color and a set of another color (usually red/blue or black/white) and they would be in a line, not a circle. IE: There would be 4 red and 3 blue.
|
this is a really nice problem. we need to find a one to one mapping between the distribution of hats and the distribution of guesses.
i think the way to solve is to break it down into simpler case, for two hats, three hats, and then generalize to 7.
EDIT SOLUTION FOR THREE HATS:
+ Show Spoiler + Let's say three colors, color 1, color 2, and color 3. The prisoners arrange themselves as prisoner 1, 2 and 3. Each prisoner has a different strategy, which combined will let them live.
Case 1: both hats you see are same color (11, 22, or 33) prisoner 1 writes down the same color prisoner 2 writes down color of one greater prisoner 3 writes down color of two greater
for example, if you see that the other hats are both color 1, (if you see 11): --prisoner 1 writes down hat 1 (same) --prisoner 2 writes down hat 2 (one greater) --prisoner 3 writes down hat 3 (two greater)
If you see 22 --prisoner 1 writes down 2 (same) --prisoner 2 writes down 3 (one greater) --prisoner 3 writes down 1 (two greater)
If you see 33 --prisoner 1 writes down 3 --2 writes down 1 --3 writes down 2
Case 2: if the hats you see are different color (12, 23, or 31) prisoner 1 writes down the remaining color prisoner 2 writes down the the left color prisoner 3 writes down the right color
*note i don't mean traditional left and write.
for example if you see 12 --1 writes down 3 --2 writes down 1 --3 writes down 2
if you see 23 --1 writes down 1 --2 writes down 2 --3 writes down 3
if you see 31 --1 writes down 2 --2 writes down 3 --3 writes down 1
This strategy will cover all 3^3 = 27 possibilities.
for cases where all numbers are same, prisoner 1 guesses right 111, 222, 333
for cases where all numbers are different, prisoner 1 guesses right 123, 231, 312 132, 213, 321 (symmetrical to first)
for cases where two numbers are same, then either prisoner 2 or prisoner 3 will guess right (prisoner 2 first case, prisoner 3 second case) 121, 113 (prisoner 2 sees 11, so he guesses 2. prisoner 3 sees 11, so he guesses 3) 232, 221 313, 332
112, 131 (prisoner 2 sees 12, so he guesses 1. prisoner 3 sees 31, so he guesses 1) 223, 212 331, 323
211, 311 (symmetrical to case above, since person 2 still sees 12, person 3 still sees 31) 322, 122 133, 233
And those are all the cases.
|
The riddle is impossible because here's what would really happen:
King: ...But there is a mathematical method where your chances of survival are 100% Prisoners: Great! Let's solve it *5 blog pages later* Prisoners: ...Screw it. The king's just trolling us, so let's just get this over with and start guessing.
|
Hyrule18888 Posts
On September 10 2010 06:57 Slithe wrote:Show nested quote +On September 10 2010 06:56 tofucake wrote:On September 10 2010 06:54 KarlSberg~ wrote:First I really thought that would be going to be something retarded, but that's actually a very nice problem. I think this is the strategy, even though I have a hard time proving it + Show Spoiler + Assign a number to each color (0..6) Assign a number to each prisoner (0..6) Each prisonner adds the colors he sees on all other guys + his number Sum%7 gives the color the prisoner has to announce In any possible case one (exactly one) prisoner will be right.
And once again, what if the King has a 120 pack of Crayolas? Also, the OP states there could be 2 reds and 1 of 5 other colors. They know ahead of time what the 7 possible colors are. Didn't you also state that there could be multiples? So would this make sense:
Possible red, orange, yellow, green, blue, indigo, violet Actual red, red, red, yellow, blue, indigo, indigo Or would it have to be
Possible red, red, red, yellow, blue, indigo, indigo Actual red, red, red, yellow, blue, indigo, indigo
|
After thinking about the problem for a while, I'm convinced there's actually hundreds (of thousands?) of solutions (just like there are 2 solutions to the 2 person problem), based on people picking a certain color based solely on the colors of their opponents. So maybe if he saw colors 1,1,3,6,5,3 in that order he'd pick color 2, and then person 2 would pick 7 and person 3 would pick... etc until someone got it right. And they'd come up with combinations for every situation. All 7^7 of them. We could plug that into a supercomputer and find one of the many answers, but the trick is finding the "simplest" solution. (One that the prisoners could memorize).
So far I've had no luck, but it has to be simple enough that there is a pattern involved, otherwise the puzzle would be nearly impossible.
|
@Tofucake The first one is possible, 7 colors are announced but not all of them have to be present in the actual set.
|
I'm not sure if this is considered communicating so maybe it's not correct, but it should be on the right track at the very least.
+ Show Spoiler + before sitting down, everyone agrees to only consider one person's hat, person A. Then, they will each assign each other a color based on the 7 colors available. If person A is wearing red, person B will be the first to give his paper to the king; it doesn't matter what person B guesses. Then person A knows his hat is red. If person A's hat is orange, person C will be the first to give his paper to the king, and person A will know his hat is orange, and so on. If person A is wearing the 7th color that is assigned to him, nobody will turn in the paper to the king and person A will know his hat is the 7th color.
edit: aww I guess I was beaten while thinking/writing this up. At least I was kind of close.
|
On September 10 2010 06:54 KarlSberg~ wrote:First I really thought that would be going to be something retarded, but that's actually a very nice problem. I think this is the strategy, even though I'm having a hard time proving it + Show Spoiler +Assign a number to each color (0..6) Assign a number to each prisoner (0..6) Each prisonner adds the colors he sees on all other guys + his number Sum%7 gives the color the prisoner has to announce In any possible case one (exactly one) prisoner will be right.
Nice work
|
@Kaze
They each guess individually, otherwise that would be communicating.
|
On September 10 2010 06:54 KarlSberg~ wrote:+ Show Spoiler +Assign a number to each color (0..6) Assign a number to each prisoner (0..6) Each prisonner adds the colors he sees on all other guys + his number Sum%7 gives the color the prisoner has to announce In any possible case one (exactly one) prisoner will be right.
nice solution Why didn't I notice the (small hint for people who want to solve it themselves)+ Show Spoiler + in the 2-player solution.
The next challenge: prove that the solution by KarlSberg is correct :-)
|
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.
|
On September 10 2010 06:58 tofucake wrote: So I won? Sweet.
This problem actually does seem like a mashup of several problems. All of the "prisoners with hats" problems I've heard were limited to a set of 1 color and a set of another color (usually red/blue or black/white) and they would be in a line, not a circle. IE: There would be 4 red and 3 blue.
yeah i'm familiar with that kind of hat problem but i've never heard of a problem with 7 hat colors before.
|
Guys this is really easy: + Show Spoiler + Assign each color a value 0-6. Each person takes sum of all the colors he sees and says the result in mod 7 (says the corresponding color to the sum). If you let a_1 be the first person's color, a_2 second guy's, etc, and S the sum of all, the first person will say S-a_1 (mod 7), second S-a_2, etc. Now it is possible to express all a_2, a_3, ... a_7 in terms of a_1. Add all values (expressed in terms of a_1) and you get 7a_1 + X, for some X. X = S (mod 7). Now the only thing the last person has to do is subtract and get his color.
|
|
|
|