|
LunarDestiny has the right idea..
+ Show Spoiler +If Guy1 sees 6 different colors, he picks the one not there, then the other 6 guys know to ALL pick one of the 6 colors.
If Guy1 sees 5 different colors, he picks one not there, and if Guy2 sees 5 different colors, he knows to pick the other not there, then everyone else knows to ALL pick one of the 5 colors.
And so on... until the last scenario where Guy1 sees only one color, so he'll pick one not there. Guy2 will see one color, he'll pick the second one not there, and so on until Guy7 sees 1 color, but everyone already guessed the other 6 colors so he knows no one else sees those 6 colors, so he picks the 1 color he sees.
I'm sure there's a better way of phrasing it though...=P
|
On September 10 2010 06:35 BottleAbuser wrote:
Since we're given that the naive strategy (completely random guesses) will achieve a success rate of ~66%, I'll assume that the hat distribution is also completely random.
Since there is no communication between the prisoners, for each prisoner, the other prisoners' answers cannot affect his own. Therefore, he ONLY has the knowledge of the other prisoners' hats. Based on this information, he must somehow improve his chances of guessing his color correctly to over 1/7.
nope. he does not have to aim at improving the chance of increasing his own hat color, all the 7 as a collective have to maximize the chance of 1 of them guessing correct. this is an important difference. i just dont know yet how to approach this problem 
|
Seeing the others' hats doesn't do anything. Think of it like this.
You throw nine 6-sided dice on the table. You throw a tenth one on the floor, under the table.
You look at the nine dice. Can you think of a strategy for guessing what the tenth one rolled, one that increases your chances of guessing it over 1/6? Answer: obviously no. They're independent events.
|
Maybe if I describe a two person solution, you guys will believe that such an answer is possible.
Do not look if you don't want hints.
+ Show Spoiler +
Two hat colors, black and white.
Guy X's strategy:
If he sees black, he guesses black.
If he sees white, he guesses white.
Guy Y's strategy:
If he sees black, he guesses white.
If he sees white, he guesses black.
Hat combinations:
BB -> X gets it right
BW -> Y gets it right
WB -> Y gets it right
WW -> X gets it right
|
On September 10 2010 06:40 Happy.fairytail wrote:LunarDestiny has the right idea.. + Show Spoiler +If Guy1 sees 6 different colors, he picks the one not there, then the other 6 guys know to ALL pick one of the 6 colors.
If Guy1 sees 5 different colors, he picks one not there, and if Guy2 sees 5 different colors, he knows to pick the other not there, then everyone else knows to ALL pick one of the 5 colors.
And so on... until the last scenario where Guy1 sees only one color, so he'll pick one not there. Guy2 will see one color, he'll pick the second one not there, and so on until Guy7 sees 1 color, but everyone already guessed the other 6 colors so he knows no one else sees those 6 colors, so he picks the 1 color he sees. I'm sure there's a better way of phrasing it though...=P
no, as i pointed out before: even if x prisoners know which x different colors they must be wearing, they still dont know which one of them has which color. if each of them just randomly picks one of the x feasible colors, there´s still a chance for all of them to get it wrong.
|
On September 10 2010 06:41 Black Gun wrote:Show nested quote +On September 10 2010 06:35 BottleAbuser wrote:
Since we're given that the naive strategy (completely random guesses) will achieve a success rate of ~66%, I'll assume that the hat distribution is also completely random.
Since there is no communication between the prisoners, for each prisoner, the other prisoners' answers cannot affect his own. Therefore, he ONLY has the knowledge of the other prisoners' hats. Based on this information, he must somehow improve his chances of guessing his color correctly to over 1/7. nope. he does not have to aim at improving the chance of increasing his own hat color, all the 7 as a collective have to maximize the chance of 1 of them guessing correct. this is an important difference. i just dont know yet how to approach this problem
This is the correct line of thinking. As BottleAbuser mentions, there is no way for an individual to improve his independent chance of correctness, but the collective can devise a superior scheme.
|
Hyrule19228 Posts
On September 10 2010 06:27 getSome[703] wrote:Here's my best guess at an answer. It works but you may or may not argue that it involves communication. + Show Spoiler +All the prisoners before hand pick one guy. The six other players agree that if the designated prisoner is wearing a certain colored hat, one of them will begin write that hat color down on their paper (so one of the players will begin to write if the designated one is wearing a red hat, another will begin to write if he is wearing an orange hat, etc). The designated prisoner, seeing the person who is writing, will then know his hat color. If none of the prisoners are writing down anything, then his hat is the seventh color. He writes down his hat color and everyone goes free
If the King has a 120 pack of Crayolas the prisoners are fucked with your strategy.
|
I've seen that type of logic before, but I'm not 100% sure how you can apply it to a larger problem, such as with 7 people.
EDIT - to expand on this:
It's kind of like the "turning a sphere inside out" puzzle. It seems counter-intuitive, yet there is a complex solution. 7 people has 823543 different possibilites, how you could come up with a simple solution is beyond me.....
|
On September 10 2010 06:40 Happy.fairytail wrote:LunarDestiny has the right idea.. + Show Spoiler +If Guy1 sees 6 different colors, he picks the one not there, then the other 6 guys know to ALL pick one of the 6 colors.
If Guy1 sees 5 different colors, he picks one not there, and if Guy2 sees 5 different colors, he knows to pick the other not there, then everyone else knows to ALL pick one of the 5 colors.
And so on... until the last scenario where Guy1 sees only one color, so he'll pick one not there. Guy2 will see one color, he'll pick the second one not there, and so on until Guy7 sees 1 color, but everyone already guessed the other 6 colors so he knows no one else sees those 6 colors, so he picks the 1 color he sees. I'm sure there's a better way of phrasing it though...=P
I don't even understand what he is saying but I can tell it makes no sense at all.
You are prisoner #1. You see 6 red hats. Possible colors are the rainbow colors. What then? Remember: Nobody can see what you write.
Gonna write blue? Guy #2 (wearing red) would be like "durrr I see no blue/yellow/whatever" and do likewise, and so on. RIP
|
Everyone can guess the same color because at least one of the seven have to be of the color and only one prisoner needs to be right.
|
On September 10 2010 06:44 Slithe wrote:Show nested quote +On September 10 2010 06:41 Black Gun wrote:On September 10 2010 06:35 BottleAbuser wrote:
Since we're given that the naive strategy (completely random guesses) will achieve a success rate of ~66%, I'll assume that the hat distribution is also completely random.
Since there is no communication between the prisoners, for each prisoner, the other prisoners' answers cannot affect his own. Therefore, he ONLY has the knowledge of the other prisoners' hats. Based on this information, he must somehow improve his chances of guessing his color correctly to over 1/7. nope. he does not have to aim at improving the chance of increasing his own hat color, all the 7 as a collective have to maximize the chance of 1 of them guessing correct. this is an important difference. i just dont know yet how to approach this problem This is the correct line of thinking. As BottleAbuser mentions, there is no way for an individual to improve his independent chance of correctness, but the collective can devise a superior scheme.
i want to clarify, do all the prisoners hand in separate sheets of solutions, or do they all write on one sheet which they can see what others wrote but not who wrote them?
|
On September 10 2010 06:41 Slithe wrote:Maybe if I describe a two person solution, you guys will believe that such an answer is possible. Do not look if you don't want hints. + Show Spoiler +
Two hat colors, black and white.
Guy X's strategy:
If he sees black, he guesses black.
If he sees white, he guesses white.
Guy Y's strategy:
If he sees black, he guesses white.
If he sees white, he guesses black.
Hat combinations:
BB -> X gets it right
BW -> Y gets it right
WB -> Y gets it right
WW -> X gets it right
this is cheating tho. so basically i can guess red (which is the colour of the hat of person sitting left) and that person can simply guess red cuz i just guessed whichever colour he was wearing.
|
On September 10 2010 06:47 saltywet wrote:Show nested quote +On September 10 2010 06:44 Slithe wrote:On September 10 2010 06:41 Black Gun wrote:On September 10 2010 06:35 BottleAbuser wrote:
Since we're given that the naive strategy (completely random guesses) will achieve a success rate of ~66%, I'll assume that the hat distribution is also completely random.
Since there is no communication between the prisoners, for each prisoner, the other prisoners' answers cannot affect his own. Therefore, he ONLY has the knowledge of the other prisoners' hats. Based on this information, he must somehow improve his chances of guessing his color correctly to over 1/7. nope. he does not have to aim at improving the chance of increasing his own hat color, all the 7 as a collective have to maximize the chance of 1 of them guessing correct. this is an important difference. i just dont know yet how to approach this problem This is the correct line of thinking. As BottleAbuser mentions, there is no way for an individual to improve his independent chance of correctness, but the collective can devise a superior scheme. i want to clarify, do all the prisoners hand in separate sheets of solutions, or do they all write on one sheet which they can see what others wrote but not who wrote them?
Separate sheets.
|
Retard way:
Guy1 got yellow hat.
He writes down red.
King: Wrong.
Guy2: Dude, he's right. The hat is red.
King: You stupid.
Guy3: Dude, he's right.
King: You stupid also.
Guy4: Dude, he's right.
King: You stupid also.
Guy5: Dude, he's right.
King: You stupid also.
Guy6: Dude, he's right.
King: You stupid also.
Guy7: Dude, he's right.
King: Maybe I am color blind.
|
If Guy1 sees 6 different colors, he picks the one not there, then the other 6 guys know to ALL pick one of the 6 colors.
no, the other guys don't know that guy1 sees 6 different colors.
They might also see 6 different ones, or they might see that guy1 and another guy have the same color.
|
On September 10 2010 06:47 CanucksJC wrote:Show nested quote +On September 10 2010 06:41 Slithe wrote:Maybe if I describe a two person solution, you guys will believe that such an answer is possible. Do not look if you don't want hints. + Show Spoiler +
Two hat colors, black and white.
Guy X's strategy:
If he sees black, he guesses black.
If he sees white, he guesses white.
Guy Y's strategy:
If he sees black, he guesses white.
If he sees white, he guesses black.
Hat combinations:
BB -> X gets it right
BW -> Y gets it right
WB -> Y gets it right
WW -> X gets it right
this is cheating tho. so basically i can guess red (which is the colour of the hat of person sitting left) and that person can simply guess red cuz i just guessed whichever colour he was wearing.
Their guesses are not based on what the other person said. They guess only based on what color they see on the other person's hat. Reread the solution, it doesn't involve them hearing each other say anything.
|
Use the adversary argument.
Suppose that the king can actually change the color of an individual's hat if he wants.
Is there a strategy that the prisoners can use, that will make sure that such a change will be provable by the individual whose hat was changed?
Remember, the only information you have is the other prisoners' hats. And you can't affect the other prisoners' answers, only your own. The other prisoners' hats are random noise. They have absolutely no bearing on what your own hat is.
Each prisoner is looking at the exact same situation.
Let's say that we change this symmetry a little bit by introducing a preset plan:
Prisoner 1 will always guess red if he sees exactly one other red hat, green if he sees exactly 2 of any given color, blue if he sees 3, and so on.
Prisoner 2 will start with red if he sees exactly 2 of any given color, green if he sees 3, and so on.
Prisoner 3 will start with red if he sees 3 hats of a given color, and so on.
Well? Does that improve their chances? No, no it doesn't do a damn thing. Because they're independent events. The information you're given has no bearing on the decision you're making.
|
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.
|
Hyrule19228 Posts
|
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?
|
|
|
|
|
|
EPT
