A hundred tourists
Moderators: jestingrabbit, Moderators General, Prelates
A hundred tourists
I'm making some math puzzles for a book I'm writing. I already posted one (14 prisons). Here's another one (a mod of a popular puzzle). I'd appreciate comments besides solutions: How hard did you find that one? Do you want me to post more like this? That I'm awesome (or perhaps, that I suck)... Stuff like that
A ship with a hundred tourists crashed near an island inhabited by cannibals. Needless to say the tourists were all captured. The cannibals told the tourists that the following day they would be arranged in a circle and each one will be given a hat in one of three colors: red, white and blue. Each tourist would be able to see 99 hats (all except for his). The cannibals would then choose a random tourist and ask him the color of his hat. Then choose another one, and so on. If a tourist guesses his hat color, he will be freed. If not, he'll be eaten.
There is no specified order in which the tourists will be asked for their hat colors. There is no specified number of hats for each color. There is even no guarantee that each color would be present. The tourists can only answer one of the three colors and only when asked. A different answer (like "green"), talking without being asked, or signaling with gestures would cause all tourists to be eaten.
The tourists had one day to come up with a strategy for their answers and came up with the best one. What was their strategy, and given a worst case scenario for it, what is the number of tourists that would be saved?
A ship with a hundred tourists crashed near an island inhabited by cannibals. Needless to say the tourists were all captured. The cannibals told the tourists that the following day they would be arranged in a circle and each one will be given a hat in one of three colors: red, white and blue. Each tourist would be able to see 99 hats (all except for his). The cannibals would then choose a random tourist and ask him the color of his hat. Then choose another one, and so on. If a tourist guesses his hat color, he will be freed. If not, he'll be eaten.
There is no specified order in which the tourists will be asked for their hat colors. There is no specified number of hats for each color. There is even no guarantee that each color would be present. The tourists can only answer one of the three colors and only when asked. A different answer (like "green"), talking without being asked, or signaling with gestures would cause all tourists to be eaten.
The tourists had one day to come up with a strategy for their answers and came up with the best one. What was their strategy, and given a worst case scenario for it, what is the number of tourists that would be saved?
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames
Re: A hundred tourists
whoops, search for "blue eyes".
EDIT: NEVER MIND. hehe. I should probably read more than 2 sentences before responding, eh?
EDIT: NEVER MIND. hehe. I should probably read more than 2 sentences before responding, eh?
Adam
Re: A hundred tourists
If all the tourists can hear what the others answer :
If not :
Spoiler:
If not :
Spoiler:
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: A hundred tourists
Yat wrote:If not :Spoiler:
I think the day to strategise means that they're okay actually.
This one is an easier case of the same problem with n people and n possible colors... having already seen the answer I can't really comment on how difficult it is.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: A hundred tourists
Yeah, I guess they could come up with a strategy to avoid the zero survivors scenario, but without having additionnal information from what the others say or what the cannibals do to them, I don't really see how they could individually escape the 2/3 dying probability...jestingrabbit wrote:I think the day to strategise means that they're okay actually.
I have seen a lot of problems of this type, but this one, whithout any information exchange, and where every prisonner gambles his own life individually, does not seem to be an easier case of any problem I know. Could you be more specific ?
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: A hundred tourists
Yat wrote:Yeah, I guess they could come up with a strategy to avoid the zero survivors scenario, but without having additionnal information from what the others say or what the cannibals do to them, I don't really see how they could individually escape the 2/3 dying probability...jestingrabbit wrote:I think the day to strategise means that they're okay actually.
Yeah, that seems right. It needs to be clear that they hear each othe'rs guesses, or at least the first, to get a better than 1/3 survival.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: A hundred tourists
jestingrabbit wrote:Yat wrote:If not :Spoiler:
I think the day to strategise means that they're okay actually.
This one is an easier case of the same problem with n people and n possible colors... having already seen the answer I can't really comment on how difficult it is.
jestingrabbit wrote:Yat wrote:Yeah, I guess they could come up with a strategy to avoid the zero survivors scenario, but without having additionnal information from what the others say or what the cannibals do to them, I don't really see how they could individually escape the 2/3 dying probability...jestingrabbit wrote:I think the day to strategise means that they're okay actually.
Yeah, that seems right. It needs to be clear that they hear each othe'rs guesses, or at least the first, to get a better than 1/3 survival.
I'm guessing you were thinking of a similar but different scenario where death or survival is determined for the whole group as a block, and declining to guess is an option. In that problem survival requires at least one correct guess out of the whole group and no incorrect guesses, and the optimal strategy arranges to group up all the incorrect guesses and spread out the correct guesses  overwhelming probability of one correct guess while everyone else declines to guess, slight probability of everyone guessing wrong at once. Overall equal expected average numbers of correct and incorrect guesses, but distributed in such a way as to drastically skew the probability of beating the problem.
For the problem at hand, with individual survival determined by the person's own mandatory guess, your later post is correct that knowledge of previous guesses is required to form a useful strategy.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: A hundred tourists
I did indeed think that one correct guess was enough to save them all. Reading comprehension fail on my part. Yat solves for the case where each individual decides their own fate, and they can hear the other respondents. In the case where they can't hear each other though, a 1/3 survival is possible, if they arrange for
Spoiler:
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: A hundred tourists
jestingrabbit wrote:I did indeed think that one correct guess was enough to save them all. Reading comprehension fail on my part. Yat solves for the case where each individual decides their own fate, and they can hear the other respondents. In the case where they can't hear each other though, a 1/3 survival is possible, if they arrange forSpoiler:
And note that this actually
Spoiler:
This is similar to the problem where there are infinitely many and you win if only finitely many are wrong (and they can't hear each other)
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
Re: A hundred tourists
I'm pretty sure you can strategise to get more than 1/3 success rate where they don't hear each other:
Spoiler:

 Posts: 2
 Joined: Sun Jul 17, 2011 10:08 pm UTC
Re: A hundred tourists
Could someone explain why the method of assigning values to each color, and then using the modulo 3 to pick a value/color works? I'm afraid I don't see why.
Re: A hundred tourists
Imagine you are one of the prisonners, and you see 27 red hats, 31 white hats and 41 blue hats. The value you see is 31+2*41 = 113 (congruent to 2 modulo 3).
Now you are lucky and you are not the first one to be picked. The guy has a white hat, so the value he sees is 112 + the value of your own hat. 112 modulo 3 is 1, so of you have a red hat his modulo will be 1 (still 112), if you have a white hat it will be 2 (112 + 1 = 113), and if you have a blue hat it will be 0 (112+2 = 114). In other words, if he says white your hat is red, if he says blue your hat is white, and if he says red your hat is blue. Every other prisonner can make the same reasonning with what he sees, and everybody except the first guy is sure to live.
Now you are lucky and you are not the first one to be picked. The guy has a white hat, so the value he sees is 112 + the value of your own hat. 112 modulo 3 is 1, so of you have a red hat his modulo will be 1 (still 112), if you have a white hat it will be 2 (112 + 1 = 113), and if you have a blue hat it will be 0 (112+2 = 114). In other words, if he says white your hat is red, if he says blue your hat is white, and if he says red your hat is blue. Every other prisonner can make the same reasonning with what he sees, and everybody except the first guy is sure to live.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: A hundred tourists
A version of this problem is similar to another thread, since I can't remember which one, I will explain it here. A group of cannibals capture three heroes, and the three heroes each get a hat. The hats are either red or blue, and each person has to guess what hat they are wearing. A third option is also allowed, in which you abstain from guessing. If at least one person gets it right and none get it wrong, they will be freed, if not, they will be eaten. They are allowed one day beforehand to decide their strategy. However, the cannibals also hear their strategy and arrange the hats so that the plan has the lowest chance of working. What is the right strategy that gives them the best chance of escape?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: A hundred tourists
I have an idea for a solution that will save more than 1/3 of the prisoners most of the time, my idea is simply that each prisoner guesses the color of the hat that he sees the most of. This solution, on deeper analysis, works for all but the cases where the two most common colors differ by one or less in their respective amounts. Can anyone improve on this?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: A hundred tourists
tomtom2357 wrote:A version of this problem is similar to another thread, since I can't remember which one, I will explain it here...
The thread you're looking for is viewtopic.php?f=3&t=76500 . I recall an older thread (which I can't find right now) which dealt with the same problem, yet no villain.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: A hundred tourists
Gwydion wrote:tomtom2357 wrote:A version of this problem is similar to another thread, since I can't remember which one, I will explain it here...
The thread you're looking for is viewtopic.php?f=3&t=76500 . I recall an older thread (which I can't find right now) which dealt with the same problem, yet no villain.
Yes, that's the one! I am working on a better solution to the problem than above, but I can't figure out how to get past the worstcase scenario. Maybe if I try for a nonsymmetric solution then that will work.
Edit: Eureka! If the person sees more than 32 red hats, guess red, if not, then if the person sees more than 32 blue hats, then guess blue, if not, then if the person sees more than 32 white hats, guess white. This works for all cases with a minimum of 33 prisoners let free!
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: A hundred tourists
tomtom2357 wrote:Yes, that's the one! I am working on a better solution to the problem than above, but I can't figure out how to get past the worstcase scenario. Maybe if I try for a nonsymmetric solution then that will work.
Edit: Eureka! If the person sees more than 32 red hats, guess red, if not, then if the person sees more than 32 blue hats, then guess blue, if not, then if the person sees more than 32 white hats, guess white. This works for all cases with a minimum of 33 prisoners let free!
I'm not sure if you've digressed to the problem in the linked thread (which is actually quite different from the one in this thread). The solution presented by Yat in the third post is the "best" solution and guarantees 99 prisoners are let free in every case.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: A hundred tourists
Trebla wrote:tomtom2357 wrote:Yes, that's the one! I am working on a better solution to the problem than above, but I can't figure out how to get past the worstcase scenario. Maybe if I try for a nonsymmetric solution then that will work.
Edit: Eureka! If the person sees more than 32 red hats, guess red, if not, then if the person sees more than 32 blue hats, then guess blue, if not, then if the person sees more than 32 white hats, guess white. This works for all cases with a minimum of 33 prisoners let free!
I'm not sure if you've digressed to the problem in the linked thread (which is actually quite different from the one in this thread). The solution presented by Yat in the third post is the "best" solution and guarantees 99 prisoners are let free in every case.
Sorry, I haven't digressed, I'm working on the assumption that none of the prisoners can hear what the others are saying. Also, my solution need a little twerking, but I have now found the solution that saves at least 33 prisoners in the worst case. If a prisoner sees at least 32 red hats, then guess red, if not, then if the prisoner sees at least 32 blue hats, then guess blue, otherwise, they will definitely see at least 32 white hats, and therefore guess white. This will save at least 33 prisoners!
Edit, actually, this won't save at least 33 prisoners, the 323234 case doesn't work (only that case doesn't work, it seems that its just 1 case every time that doesn't work!), I will get back to you when I have a better solution.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: A hundred tourists
tomtom2357 wrote:Sorry, I haven't digressed, I'm working on the assumption that none of the prisoners can hear what the others are saying. Also, my solution need a little twerking, but I have now found the solution that saves at least 33 prisoners in the worst case. If a prisoner sees at least 32 red hats, then guess red, if not, then if the prisoner sees at least 32 blue hats, then guess blue, otherwise, they will definitely see at least 32 white hats, and therefore guess white. This will save at least 33 prisoners!
Edit, actually, this won't save at least 33 prisoners, the 323234 case doesn't work (only that case doesn't work, it seems that its just 1 case every time that doesn't work!), I will get back to you when I have a better solution.
Now I follow you...
There are more cases that don't work for this plan.
Any case where the largest number of colored hats is the same.
E.g., 40 red, 40 blue, 20 white. Every Red will see 39 red and 40 blue, therefore they will guess blue. And every blue will see 40 red and 39 blue and therefore guess red. Every white will see an even number of blue/white and randomly guesses either blue or white. Number saved : 0/100
Re: A hundred tourists
Trebla wrote:tomtom2357 wrote:Sorry, I haven't digressed, I'm working on the assumption that none of the prisoners can hear what the others are saying. Also, my solution need a little twerking, but I have now found the solution that saves at least 33 prisoners in the worst case. If a prisoner sees at least 32 red hats, then guess red, if not, then if the prisoner sees at least 32 blue hats, then guess blue, otherwise, they will definitely see at least 32 white hats, and therefore guess white. This will save at least 33 prisoners!
Edit, actually, this won't save at least 33 prisoners, the 323234 case doesn't work (only that case doesn't work, it seems that its just 1 case every time that doesn't work!), I will get back to you when I have a better solution.
Now I follow you...
There are more cases that don't work for this plan.
Any case where the largest number of colored hats is the same.
E.g., 40 red, 40 blue, 20 white. Every Red will see 39 red and 40 blue, therefore they will guess blue. And every blue will see 40 red and 39 blue and therefore guess red. Every white will see an even number of blue/white and randomly guesses either blue or white. Number saved : 0/100
No, by his rules, all 100 tourists will guess red. It's not that they guess whichever they see the most of, it's if they see some number (or greater) of red, then guess red. Otherwise, perform the same test with blue. If they still have not guessed, then they are guaranteed to guess white.
Slight nitpick, it would be a 323236 case (there are 100 tourists, not 98). And, I'm not readily coming up with a strategy similar to your originally proposed solution that doesn't fall into the same trap that your current one does.
Re: A hundred tourists
I can think of a solution that saves at least half of the group (if they can hear what others are saying, and they are eaten immediately)
The first person asked responds with the color of the hat of the person to their right. That person remembers the color.
For everyone else, if the person to your left has already been asked, you respond with that color, if not you respond with the color of the person on your right.
Ultimately, Once they've asked 50% of the people, even assuming they were all wrong, the other 50% now know their hat color.
The first person asked responds with the color of the hat of the person to their right. That person remembers the color.
For everyone else, if the person to your left has already been asked, you respond with that color, if not you respond with the color of the person on your right.
Ultimately, Once they've asked 50% of the people, even assuming they were all wrong, the other 50% now know their hat color.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: A hundred tourists
burgie12 wrote:Trebla wrote:tomtom2357 wrote:Sorry, I haven't digressed, I'm working on the assumption that none of the prisoners can hear what the others are saying. Also, my solution need a little twerking, but I have now found the solution that saves at least 33 prisoners in the worst case. If a prisoner sees at least 32 red hats, then guess red, if not, then if the prisoner sees at least 32 blue hats, then guess blue, otherwise, they will definitely see at least 32 white hats, and therefore guess white. This will save at least 33 prisoners!
Edit, actually, this won't save at least 33 prisoners, the 323234 case doesn't work (only that case doesn't work, it seems that its just 1 case every time that doesn't work!), I will get back to you when I have a better solution.
Now I follow you...
There are more cases that don't work for this plan.
Any case where the largest number of colored hats is the same.
E.g., 40 red, 40 blue, 20 white. Every Red will see 39 red and 40 blue, therefore they will guess blue. And every blue will see 40 red and 39 blue and therefore guess red. Every white will see an even number of blue/white and randomly guesses either blue or white. Number saved : 0/100
No, by his rules, all 100 tourists will guess red. It's not that they guess whichever they see the most of, it's if they see some number (or greater) of red, then guess red. Otherwise, perform the same test with blue. If they still have not guessed, then they are guaranteed to guess white.
Slight nitpick, it would be a 323236 case (there are 100 tourists, not 98). And, I'm not readily coming up with a strategy similar to your originally proposed solution that doesn't fall into the same trap that your current one does.
You're right of course, 323236 is the valid counterexample (actually, anytime where there are exactly 32 prisoners with red hats is a counterexample to my above solution)
Right now I'm having trouble saving even one prisoner, I am currently working on each prisoner guessing based on the prisoners beside him/her. What I have come up with is this:
If you see the two prisoners to your left and right wearing red, guess red. Else, if you see the two prisoners to your left wearing red. guess blue, else, if you see the prisoner two to your left wearing red, and the prisoner 1 to your left not wearing red, guess red. (at this point, if the cannibals place two people with red hats two away from each other, one of the prisoners will guess correctly). Else, if you see the two prisoners to your right wearing red, guess white. Else, if you see the prisoner to your right wearing red, the prisoner two to your right wearing white, and the prisoner to your left wearing blue, guess red. I am still figuring out the remaining cases though.
Also, rokkshark, they have already figured out how to save 99 people with them hearing each other, the real problem is where they can't hear each other.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: A hundred tourists
burgie12 wrote:No, by his rules, all 100 tourists will guess red. It's not that they guess whichever they see the most of, it's if they see some number (or greater) of red, then guess red. Otherwise, perform the same test with blue. If they still have not guessed, then they are guaranteed to guess white.
My mistake, I misinterpreted the explanation to be an example rather than an explicit solution and misunderstood.

 Posts: 9
 Joined: Mon Sep 08, 2008 4:15 am UTC
Re: A hundred tourists
I'm digressing from the simple logic puzzle model, but since (as far as I can tell) Yat has presented an excellent solution, I'm just going to continue on a slightly whimsical train of thought a little...
I think the biggest problem would likely be explaining the concept of modular arithmetic to a random selection of people on a ship. Let's suppose that there's a chance that people mess up the maths.
Person 1, Andy, messes up his count. He gets eaten (2/3 chance, same as before), but now the rest of the group is now working off an erroneous number (we'll call this number K, the number off which everybody is basing their guesses for their own hats). Assuming the second person to get picked, Bella, does her math correctly, she will get eaten with a 2/3 chance. If she does her math wrong, still a 2/3 chance of being lunch.
Now if Bella is eaten, then everybody knows that somebody messed up (assuming they discussed this eventuality beforehand). How do they proceed?
Even worse, assume Andy messed up, Bella got lucky (1/3 chance) and Charlie, person 3, gets eaten! did Charlie mess up, or was it Andy?
If Andy messed up, then they are all working off the wrong number. If Andy didn't mess up but Bella did, then they have the correct number and assuming that their perform the right math, problem solved, shame about Bella. Now the maths they all perform is more or less identical in complexity, so the only real factor that they have to base their guesses as to who messed up is the relative mathematical skills of everybody. If Bella is a maths teacher, and Andy is a literature major, then it's more likely that Andy messed up and they all need a new number. If it's the other way around and Andy is the genius while Bella flips burgers, then they're probably all okay.
So the first order of business, in the day before, is establishing who's good at maths and who isn't, perhaps with a quiz, or just people being honest and estimating their own mathematical abilities. Next, create a ranking that people have to try and memorize of who is better than who at maths.
When somebody N people after the person to provide K, ie Andy in the first case, gets eaten (so N=1 for Bella, 2, for Charlie, etc), the fault could either lie with them or Andy. The probability that Andy messed up decreases by a factor of 1/3 with every increase in N (I think this is right, I would be happy to be corrected or have this proved. I'll try myself as well). This makes intuitive sense, if Kesha (N=10) gets eaten the chance than Andy messed up and everybody between them got lucky is pretty slim, and the chance of somebody getting lucky off a wrong value of K is 1/3. so in the long run we can be pretty sure that if everybody (except poor Andy of course) is fine and then the 30th person (who shall remain nameless) gets eaten, it's likely their own fault for messing up the maths.
But if Bella or Charlie or even miss Daisy is eaten, there's a decent chance that Andy screwed up and they're all in danger. What to do now? if we have quantitative numbers for the relative mathematical skill of Andy and our unlucky second victim, we can work our the likelihood of our value K being wrong. If we think K is wrong, we need a new K, so somebody soon is going to have to ignore their guess of hat based on Andy's K, calculate their own K, and use that instead, hoping that they get lucky.
Some more thoughts:
What other indications might there be of K being wrong?
How would you know that you've been given a new value of K?
Would anybody sacrifice themselves to yell out various colours of hats before being eaten by the cannibals?
TL;DR people are bad at maths and it could get them eaten.
I think the biggest problem would likely be explaining the concept of modular arithmetic to a random selection of people on a ship. Let's suppose that there's a chance that people mess up the maths.
Person 1, Andy, messes up his count. He gets eaten (2/3 chance, same as before), but now the rest of the group is now working off an erroneous number (we'll call this number K, the number off which everybody is basing their guesses for their own hats). Assuming the second person to get picked, Bella, does her math correctly, she will get eaten with a 2/3 chance. If she does her math wrong, still a 2/3 chance of being lunch.
Now if Bella is eaten, then everybody knows that somebody messed up (assuming they discussed this eventuality beforehand). How do they proceed?
Even worse, assume Andy messed up, Bella got lucky (1/3 chance) and Charlie, person 3, gets eaten! did Charlie mess up, or was it Andy?
If Andy messed up, then they are all working off the wrong number. If Andy didn't mess up but Bella did, then they have the correct number and assuming that their perform the right math, problem solved, shame about Bella. Now the maths they all perform is more or less identical in complexity, so the only real factor that they have to base their guesses as to who messed up is the relative mathematical skills of everybody. If Bella is a maths teacher, and Andy is a literature major, then it's more likely that Andy messed up and they all need a new number. If it's the other way around and Andy is the genius while Bella flips burgers, then they're probably all okay.
So the first order of business, in the day before, is establishing who's good at maths and who isn't, perhaps with a quiz, or just people being honest and estimating their own mathematical abilities. Next, create a ranking that people have to try and memorize of who is better than who at maths.
When somebody N people after the person to provide K, ie Andy in the first case, gets eaten (so N=1 for Bella, 2, for Charlie, etc), the fault could either lie with them or Andy. The probability that Andy messed up decreases by a factor of 1/3 with every increase in N (I think this is right, I would be happy to be corrected or have this proved. I'll try myself as well). This makes intuitive sense, if Kesha (N=10) gets eaten the chance than Andy messed up and everybody between them got lucky is pretty slim, and the chance of somebody getting lucky off a wrong value of K is 1/3. so in the long run we can be pretty sure that if everybody (except poor Andy of course) is fine and then the 30th person (who shall remain nameless) gets eaten, it's likely their own fault for messing up the maths.
But if Bella or Charlie or even miss Daisy is eaten, there's a decent chance that Andy screwed up and they're all in danger. What to do now? if we have quantitative numbers for the relative mathematical skill of Andy and our unlucky second victim, we can work our the likelihood of our value K being wrong. If we think K is wrong, we need a new K, so somebody soon is going to have to ignore their guess of hat based on Andy's K, calculate their own K, and use that instead, hoping that they get lucky.
Some more thoughts:
What other indications might there be of K being wrong?
How would you know that you've been given a new value of K?
Would anybody sacrifice themselves to yell out various colours of hats before being eaten by the cannibals?
TL;DR people are bad at maths and it could get them eaten.
Re: A hundred tourists
Don't we know K as close as K+2?
as long as 1 person is saved and we know the color he guessed we know what mod he guessed even if we don't know how he got to it.
Hmm no, spoilered my poor thinking.
What if we get 3 correct guess's in a row? even if they are guess's would that be enough information to work out k?
as long as 1 person is saved and we know the color he guessed we know what mod he guessed even if we don't know how he got to it.
Hmm no, spoilered my poor thinking.
Spoiler:
What if we get 3 correct guess's in a row? even if they are guess's would that be enough information to work out k?
R3sistance  I don't care at all for the ignorance spreading done by many and to the best of my abilities I try to correct this as much as I can, but I know and understand that even I can not be completely honest, truthful and factual all of the time.

 Posts: 9
 Joined: Mon Sep 08, 2008 4:15 am UTC
Re: A hundred tourists
krogoth wrote:What if we get 3 correct guess's in a row? even if they are guess's would that be enough information to work out k?
Roughly, the probability of 3 people guessing right in a row, without having a correct value of K (making their guesses more or less random) is (1/3)^3 =~4%. Pretty unlikely, but not impossible.
I think that if somebody "guesses" their hat correctly, all we know is the colour of their hat, so we gain nothing. If we know that that person's guess was not random, but rather based on some prior knowledge (ie K), then we can infer that their prior knowledge was correct, and so we can use K ourselves.
I'm afraid I'm having a hard time following your logic in your spoiler, krogoth. What do you mean when you say
krogoth wrote:Spoiler:
Maybe you've just worked something out that I haven't seen yet, but surely our own hat is completely independent of what we see?
 Kingreaper
 Posts: 169
 Joined: Sun Jan 27, 2008 4:23 pm UTC
Re: A hundred tourists
Going for the bonus problem: What if they're not perfect at maths.
I'm assuming they all have the same probability of doing the maths wrong, because the problems where they have different chances (and each knows the others chances) are many and varied.
I'm assuming they all have the same probability of doing the maths wrong, because the problems where they have different chances (and each knows the others chances) are many and varied.
Spoiler:
 DaBigCheez
 Posts: 788
 Joined: Tue Jan 04, 2011 8:03 am UTC
Re: A hundred tourists
rokkshark wrote:I can think of a solution that saves at least half of the group (if they can hear what others are saying, and they are eaten immediately)
The first person asked responds with the color of the hat of the person to their right. That person remembers the color.
For everyone else, if the person to your left has already been asked, you respond with that color, if not you respond with the color of the person on your right.
Ultimately, Once they've asked 50% of the people, even assuming they were all wrong, the other 50% now know their hat color.
Doesn't work reliably  if the random order turns out to be "start at one person and eat clockwise (that is, to the left) around the circle", only one person (the one to the right of the initial person asked, and thus also the one to the right of every person asked thereafter save himself) will know his color. (And it relies on hearing what others answer anyway, in which case there's a better solution.)
existential_elevator wrote:It's like a jigsaw puzzle of Hitler pissing on Mother Theresa. No individual piece is offensive, but together...
If you think hot women have it easy because everyone wants to have sex at them, you're both wrong and also the reason you're wrong.
Re: A hundred tourists
Alfonzo227 wrote:I'm afraid I'm having a hard time following your logic in your spoiler, krogoth. What do you mean when you saykrogoth wrote:Spoiler:
Maybe you've just worked something out that I haven't seen yet, but surely our own hat is completely independent of what we see?
The issue is I'm stupid and was basically thinking Yaks answer, I just worded it poorly.
assuming their value K by Alfonzo227, and we have value our own K lets calling it G,
Each time a person takes a guess it brings us closer to the correct answer, reminding me of the game of Nim.
Maybe we can twist that to help us?
I'm thinking of the manga/anime Kaiji now.
It's pretty much life or death gambling, I can't think of how to do this but I'm sure he would find a way.
R3sistance  I don't care at all for the ignorance spreading done by many and to the best of my abilities I try to correct this as much as I can, but I know and understand that even I can not be completely honest, truthful and factual all of the time.
Who is online
Users browsing this forum: No registered users and 4 guests