A hundred tourists

[wraith]

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?

[Adam H]

whoops, search for "blue eyes".

EDIT: NEVER MIND. hehe. I should probably read more than 2 sentences before responding, eh?

[Yat]

If all the tourists can hear what the others answer :

Spoiler:

let red=0, white=1 and blue=2. The first one sums all the hats he sees, and answers the color which matches this number modulo 3. He has 2/3 chances of dying, but now everybody else, knowing what is the color of the first tourist's hat, can deduce the modulo 3 of the whole group, and consequently the color of his own hat. Worst case scenario : 99 tourists saved.

If not :

Spoiler:

They're screwed. Worst case scenario : 0 tourists saved.

[jestingrabbit]

If not :

Spoiler:

They're screwed. Worst case scenario : 0 tourists saved.

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.

[Yat]

I think the day to strategise means that they're okay actually.

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...

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]

I think the day to strategise means that they're okay actually.

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...

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.

[douglasm]

If not :

Spoiler:

They're screwed. Worst case scenario : 0 tourists saved.

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.

I think the day to strategise means that they're okay actually.

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...

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]

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:

one third of the people to guess each of the modulo 3 possibilities.

[mike-l]

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:

one third of the people to guess each of the modulo 3 possibilities.

And note that this actually

Spoiler:

Guarantees exactly 1/3rd are right and 2/3 are wrong.

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)

[Adacore]

I'm pretty sure you can strategise to get more than 1/3 success rate where they don't hear each other:

Spoiler:

You have one other potential bit of information - depending on the exact setup of the puzzle (it's not clear) the tourists might be able to see if the other tourists asked were eaten or freed before they answer.

Thus, if the 100 tourists agree to take one of the modulo-3 possibilities to guess, with a second possibility as a second guess, and a third possibility as a final guess then in the worst case scenario:
- the cannibals ask someone, and the first guess modulo-3 is the wrong modulo-3, he gets eaten;
- the cannibals ask someone else. Recognising that the first tourist was wrong, he switches to the second-choice modulo-3, but that's also wrong, he gets eaten;
- all other tourists can deduce the correct modulo-3, so 98 are saved.

Obviously if the tourists don't hear the answers and the first tourist doesn't get eaten/freed before the second tourist answers (or they don't see whether he is eaten or freed), then you're probably stuck with the 1/3 case.

[fireballs619]

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.

[Yat]

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.

[tomtom2357]

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?

[tomtom2357]

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?

[Gwydion]

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.

[tomtom2357]

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 worst-case scenario. Maybe if I try for a non-symmetric 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!

[Trebla]

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 worst-case scenario. Maybe if I try for a non-symmetric 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.

[tomtom2357]

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 worst-case scenario. Maybe if I try for a non-symmetric 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 tweaking, 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 32-32-34 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.

[Trebla]

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 tweaking, 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 32-32-34 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

[burgie12]

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 tweaking, 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 32-32-34 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 32-32-36 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.

[rokkshark]

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.

[tomtom2357]

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 tweaking, 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 32-32-34 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 32-32-36 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, 32-32-36 is the valid counter-example (actually, anytime where there are exactly 32 prisoners with red hats is a counter-example 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.

[Trebla]

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.

[Alfonzo227]

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.

[krogoth]

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.

Spoiler:

as it's mod 3 we know what we see at the beginning add or minus 2 mod for our own hat.
then I would expect since we can see the hats colors of those whom are wrong I would expect after a few incorrect guess's we should be able to work it out. i see a green hat go past first to get eaten I know it's not mod 1 or mod 2, or if I see a green hat saved I know it's mod 3, at best it takes only the first correct guess to keep getting it correct?

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?

[Alfonzo227]

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

Spoiler:

as it's mod 3 we know what we see at the beginning add or minus 2 mod for our own hat.

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]

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.

Spoiler:

Assuming they can all do the following, simpler, calculation, this seems like it should work (might be optimal, but not sure):
The "giver" (the first person) gives out the information through their guess as normal.
"Guessers" 1 and 2 make guesses based on that information, as normal.

If, at any point after guesser 2, the number of correct guesses from "guessers" is less than half the number of incorrect guesses (ie. 1/3rd or less of the current guessers number) the next person becomes a new "giver", and everyone else renumbers themselves accordingly.

This system works well because the person you're asking to become a new "giver" is losing nothing by doing so: The probability of the original "giver" having been correct is less than 1/3 anyway.
So you don't even have to rely on anyone being willing to sacrifice themself; everyone can be 99.99999% selfish, and the remaining tiny bit of altruism will cause them to go "what the hell, might as well try and save the rest of them, I'm as well off doing that as I am guessing randomly".

[DaBigCheez]

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.)

[krogoth]

I'm afraid I'm having a hard time following your logic in your spoiler, krogoth. What do you mean when you say

Spoiler:

as it's mod 3 we know what we see at the beginning add or minus 2 mod for our own hat.

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.