Seventeen "Blue Eyes" Objections and Responses [SPOILER]

[Gwydion]

Given that all the inhabitants are perfect logicians, the most uniquely efficient strategy would be common knowledge, as would be the need for everyone to utilize the same strategy in order for it to work. Thus they would all instantly and independently know the earliest day they could go down to the ferry and deduce their eye colour.

Well, now you're getting into the realm of superrationality - the idea that everyone comes to the same conclusion not through any merit of its own, but because it is the "best" universally provided that everyone uses it. Superrationality, however, does not follow from "perfectly logical" behavior in many circumstances.

Also, you seem to be basing your solution on the idea that the islanders want to leave. I like to assume that leaving the island is a bad thing, but that if ever someone knew/deduced/discovered their eye color, they are forced to do so. In that case, even if I agree that your algorithm works, the islanders are never forced to go to the ferry, as they don't actually know their eye color until they get there.

[skeptical scientist]

if there are more than one strategies that are equally the most efficient, then there will be strategy that is the most 'uniquely' efficient.

What does that even mean?

[Peeling]

if there are more than one strategies that are equally the most efficient, then there will be strategy that is the most 'uniquely' efficient.

What does that even mean?

To address both yourself and the poster above:

It is common knowledge amongst the inhabitants that in order to infer their eye colour from the date of their arrival at the ferry, each individual would need to choose the same encoding schema.

Personally, I think picking the smallest possible 'base' for the number of islanders and ordering the code smallest to largest is the most efficient. No other optimisations are possible for the same reasons no optimisation of the official solution is possible: the same solution must work for every possible nested hypothetical.

Assuming I'm wrong, however, the perfect logicians on the island would know what the most efficient schema is.

On the offchance that there is more than one equally 'most efficient' schema (which I doubt), it would be common knowledge that neither schema is useful because there would be no way of knowing which another inhabitant would choose.

Therefore, they would choose the schema that is as efficient as possible whilst not being as efficient as any other schema.

Another way to think about this is to say that any schema which is in principle as efficient as a non-identical schema actually has zero efficiency, because it cannot hope to succeed other than by chance. Thus the 'most efficient' schema is by definition uniquely so.

Analogously:

Alan and Bob live in two towns connected by four different paths. Two paths take ten minutes to walk, one path takes twenty, and one thirty. They want to meet up as soon as possible, but can't communicate their intentions. Their choices are to wait for the other to arrive, or walk to the other town via one of the paths - but they only get to make their choice once, and if they miss each other or both stay home, they 'lose'. What should each do?

To me it's obvious that each should take the twenty-minute path. They shouldn't take either of the ten minute paths because of the risk of missing each other. They shouldn't take the thirty minute path because they want to meet as soon as possible. If both pick the quickest route that is also uniquely 'quick', they are guaranteed to meet.

As to the other objections about islanders not wanting to leave - fair enough. Personally, I didn't get that vibe from the puzzle; there was no mention of them being under duress and - to me at least - 'figured out' implied some kind of active interest in leaving.

[skullturf]

It is common knowledge amongst the inhabitants that in order to infer their eye colour from the date of their arrival at the ferry, each individual would need to choose the same encoding schema.

As you alluded to earlier, I think you're essentially considering a different puzzle. In the classic blue eyes puzzle, the islanders aren't "coming up with" a schema for "encoding" information about islander's eye colors. They simply know the facts that they know, and can't help deducing conclusions from them.

Alan and Bob live in two towns connected by four different paths. Two paths take ten minutes to walk, one path takes twenty, and one thirty. They want to meet up as soon as possible, but can't communicate their intentions. Their choices are to wait for the other to arrive, or walk to the other town via one of the paths - but they only get to make their choice once, and if they miss each other or both stay home, they 'lose'. What should each do?

To me it's obvious that each should take the twenty-minute path. They shouldn't take either of the ten minute paths because of the risk of missing each other. They shouldn't take the thirty minute path because they want to meet as soon as possible. If both pick the quickest route that is also uniquely 'quick', they are guaranteed to meet.

This is interesting, but it might be a digression from the notion of "perfect logician" as intended in the blue eyes puzzle. I agree that if I was Alan or Bob, I'd probably choose the twenty-minute path. But that's an action, or a decision.

Can Alan deduce the statement "Bob will take the twenty-minute path" by logic alone? Well, it depends what the premises are.

One probably could make an interesting puzzle where people are choosing among different paths, and they know statements like "The other guy will take the shortest path among all paths with unique lengths." Perhaps because that statement is a premise of the puzzle, or perhaps because it can be deduced from other premises.

But if the islanders in the blue eyes puzzle are saying things like "I'm trying to decide whether to do X or Y, but I know that other islanders would do X, so I choose to do X", I think that goes beyond the parameters of the puzzle, and beyond the idea of a perfect logician.

In the blue eyes puzzle, it could be that nobody ever "decides" to do anything. When somebody leaves the island, it could be that something in their brain clicks and they turn into a zombie. Maybe instead of leaving the island at midnight, their brain explodes at midnight and they die.

Also, with the example of the four paths, it's clear that there are a finite number of well-defined paths to choose from. I don't think it's obvious whether the analogous thing is true for the set of all "schemas" by which one could "encode" information about the eye colors one sees. (Not to mention that this type of thing might violate the "no communication" clause -- presumably they aren't allowed to do things like "if you see an odd number of people with blue eyes, raise your left hand.")

[skeptical scientist]

It is common knowledge amongst the inhabitants that in order to infer their eye colour from the date of their arrival at the ferry, each individual would need to choose the same encoding schema.

Personally, I think picking the smallest possible 'base' for the number of islanders and ordering the code smallest to largest is the most efficient. No other optimisations are possible for the same reasons no optimisation of the official solution is possible: the same solution must work for every possible nested hypothetical.

Assuming I'm wrong, however, the perfect logicians on the island would know what the most efficient schema is.

On the offchance that there is more than one equally 'most efficient' schema (which I doubt), it would be common knowledge that neither schema is useful because there would be no way of knowing which another inhabitant would choose.

Therefore, they would choose the schema that is as efficient as possible whilst not being as efficient as any other schema.

Yeah, this doesn't work.

Pick any encoding scheme, choose two encodable pieces of information a and b, and swap the codes for a and b. You get a new, different encoding scheme which is equally efficient. So there is no unique most efficient encoding, and every schema is as efficient as some different schema, so there is no way to get uniqueness out of this without some communication to agree on a scheme.

[Peeling]

It is common knowledge amongst the inhabitants that in order to infer their eye colour from the date of their arrival at the ferry, each individual would need to choose the same encoding schema.

Personally, I think picking the smallest possible 'base' for the number of islanders and ordering the code smallest to largest is the most efficient. No other optimisations are possible for the same reasons no optimisation of the official solution is possible: the same solution must work for every possible nested hypothetical.

Assuming I'm wrong, however, the perfect logicians on the island would know what the most efficient schema is.

On the offchance that there is more than one equally 'most efficient' schema (which I doubt), it would be common knowledge that neither schema is useful because there would be no way of knowing which another inhabitant would choose.

Therefore, they would choose the schema that is as efficient as possible whilst not being as efficient as any other schema.

Yeah, this doesn't work.

Pick any encoding scheme, choose two encodable pieces of information a and b, and swap the codes for a and b. You get a new, different encoding scheme which is equally efficient. So there is no unique most efficient encoding, and every schema is as efficient as some different schema, so there is no way to get uniqueness out of this without some communication to agree on a scheme.

That would be true if we were talking about the compression efficiency of the code. For instance, if we were talking about assigning a number to each of fifty different English words, yes, there are many equally efficient schema and no way to pick the best.

But that's not what we're doing. In this case the compression efficiency of the code is fixed because of the nested hypotheticals of each individual. Efficiency in this case means picking the smallest number we know will uniquely represent what we're seeing. I've actually thought of a couple of optimisations, which I'll detail below.

As I mentioned, it's common knowledge that everyone's nested hypotheticals include every possible combination of eye colour. So for (say) 100 total inhabitants everyone knows that someone could think that someone could think that <etc> someone could see 99 of any given colour. So the minimum safe 'space' to allocate in the code for each visible eye colour is two decimal digits. However, it's also common knowledge that the smallest possible code number is 99. Why? Because anyone who could see less than 99 of one colour must be able to see some of another colour too, making their code more than two decimal digits long. Given any number of eye colours, it's trivially obvious that the smallest number you can generate by thus encoding them is by arranging them smallest to largest.

Take a simpler example with just 10 people, where there are five green eyed, 3 blue eyed and two brown.

Everyone knows someone could think that <etc> someone could see 9 of any colour. So everyone knows they need to reserve one decimal digit per visible colour to ensure their code is unique to people sharing their eye colour (or who are an equal-sized group of eye colours, as dealt with in my original post). They also know they can subtract 9, because 9 is the smallest possible code anyone could come up with.

Greens see two brown, three blue and four green. The most efficient encoding for them is therefore 234 - 9 = 225.
Blues see two browns, two blues and five greens, making 225 - 9 = 216.
Browns see one brown, three blues and five greens, making 135 - 9 = 126.

Both browns go to the ferry on day 126, at which point everyone knows it's more efficient to re-evaluate than to stick with their original count (since it's common knowledge that an entire colour has just left the island, reducing everyone's visible eye colours, and thus the digits in their codes, by one).

So now there are just 8 people, making the code base 8 and the number to subtract, 7.

Greens see three blue and four green: (3*8)+(4)-7 = 21
Blues see two blue and five green: (2*8)+(5) - 7 = 14

The blues leave 14 days later. Now the base is 5 and the number to subtract, four.

Greens see four greens: (4)-4 = 0.

So all the greens go down the next day and leave. (This works because if any of them had had a different colour eye, the others would have seen 1X 3G, which encodes as (1*5)+3 - 4 = 4)

I can't think of any further safe optimisations. But if there are any, the people on the island would make them

EDIT: Actually, I can think of a further optimisation - a rather significant one.

For ten people, nobody can generate a code value smaller than nine. We also know that the largest possible code number is 111111111, where someone sees nine individual eye colours.

That got me thinking: the sum of each group of digits in the code (in the case of ten people, a 'group' is a single digit) must equal 9. So in the example above:

Greens see 2,3,4 (total of digits is 9)
Blues see 2,2,5 (total of digits is 9)
Browns see 1,3,5 (total of digits is 9)

Therefore, we only need to consider codes where the digits add up to nine (for 100 people, it would be codes where adding up all the adjacent pairs of digits gets you to 99, eg: 99,0198,0297,0396 etc)

Thus rather than waiting for 126 days, the two browns would be able to work out which, in the ascending series of possible codes, was the index of theirs:

Greens see two brown, three blue and four green. The first-pass encoding for them is therefore 234.
Blues see two browns, two blues and five greens, making 225.
Browns see one brown, three blues and five greens, making 135.

1A 1B 3C 4D

D: 1133
C: 1124
A: 134
B: 134

Based on the common knowledge that all codes must have digits that sum to 9, and the digits will always be in ascending order, we can write those codes down as follows:

9,18,27,36,45,117,126,135,144,225,234,333,1116,1125,1134,1224,1233,11115,11124,11133,11223,12222,111114,111123,111222,1111113,1111122,11111112,111111111

So the browns can go down on day 8. After that:

Green sees 3 blue 4 green, so first-pass code is (in base 8 ) 34
Blue sees 2 blue 5 green, so first-pass code is (in base 8 ) 25

Possible codes (in base 8 ) are 7,16,25,34,115,124,133,223,1114,1123,11113,11122,111112,1111111

So blues leave 3 days later.

Green sees 4 green, so first pass code is (in base 5) 4
Possible codes in base 5 are 4,13,22,112,1111

so greens leave next day.

Problem: This optimisation violates the need for uniqueness, because we are now mapping a each of a sparse list of code 'words' to a number, and there's no guarantee everyone would pick the same mapping.

I'm going to think a bit more about this, but I reckon that might be a fatal flaw in the optimised version.

[skeptical scientist]

That would be true if we were talking about the compression efficiency of the code. For instance, if we were talking about assigning a number to each of fifty different English words, yes, there are many equally efficient schema and no way to pick the best.

But that's not what we're doing.

That is exactly what you're doing. It's just that your words are things like "two brown, three blue and four green" and "two brown, two blue and five green." You say that the most efficient code for "two brown, three blue and four green" is 225, and for "two brown, two blue and five green" is 216, but one could just as easily swap the two codes, so that "two brown, two blue and five green" is 225, and "two brown, three blue and four green" is 216. If everyone who sees two brown-, three blue- and four green-eyed islanders shows up on day 216, your strategy works just as well.

[douglasm]

I'm going to short-circuit this whole discussion about what methods of "compressing" the waiting period might be best by bringing in a post from two and a half years ago where I proved no such method can even in principle exist:
This one.

The relevant portion of the post is this:

To prove that it can't be done in less than 100 days, consider it from the other direction. If the blue-eyed people leave on day X, why would they do so? The possibility of 99 blue-eyed people must have been eliminated within the past 24 hours. The guru's statement obviously doesn't do that in that short amount of time, so it has to have been eliminated some other way. The only other possible way is that if there were only 99 blue-eyed people they would have left on day X-1. Now, why would 99 blue-eyed people leave on day X-1? It must be either because of the guru's statement or because 98 people would have left on day X-2. Now, why would 98 blue-eyed people leave on day X-2? And so on.

You eventually get down to a lone blue-eyed person would leave on day X-99. It's not possible for anyone to leave before day 1, so the earliest possible date for the hypothetical loner to leave is day 1 and X cannot therefore be less than 100.

[Xias]

I'm going to short-circuit this whole discussion about what methods of "compressing" the waiting period might be best by bringing in a post from two and a half years ago where I proved no such method can even in principle exist:
This one.

The relevant portion of the post is this:

To prove that it can't be done in less than 100 days, consider it from the other direction. If the blue-eyed people leave on day X, why would they do so? The possibility of 99 blue-eyed people must have been eliminated within the past 24 hours. The guru's statement obviously doesn't do that in that short amount of time, so it has to have been eliminated some other way. The only other possible way is that if there were only 99 blue-eyed people they would have left on day X-1. Now, why would 99 blue-eyed people leave on day X-1? It must be either because of the guru's statement or because 98 people would have left on day X-2. Now, why would 98 blue-eyed people leave on day X-2? And so on.

You eventually get down to a lone blue-eyed person would leave on day X-99. It's not possible for anyone to leave before day 1, so the earliest possible date for the hypothetical loner to leave is day 1 and X cannot therefore be less than 100.

My favorite explanation/proof for why it's impossible to leave before day X for X blue eyed people is somewhat of an application of your proof.

Assume that it is possible for X blue eyed people to leave on a day N<X

Then there must be some day 1=<M=<N during which some case of Y blue eyed islanders and some case of Y-1 blue eyed islanders would leave on day M, where Y<X.

If there are Y blue-eyed people, then every blue-eyed person is then unsure on day M if it is the Y case or the Y-1 case, so they would not be able to leave. Therefore, no information can be passed on to the Y+1, Y+2, ... or X cases.

As an example, say 100 blue eyed people would leave on day 10, but 98 or 99 would have left on day 9. Since in the 99 case, nobody can leave (because it's the same day as the 98 case), then the fact they don't leave does not prove in the 100 case that they may leave on day 10 (since no information was gathered from 99 not leaving).

[Lenoxus]

Ah, I wish I'd figured out how to get email alerts on threads here, or I'd have joined the conversation about Peeling's idea; oh well. It's a neat idea but doesn't work in relation to the puzzle as originally worded.

The "aha" moment of the original puzzle is very satisfying, particularly when you see that it doesn't matter what the islanders want. Still, it's interesting to consider a variant of the problem that turns it into a game rather than a "neutral" exercise in logic, and hence involving some game theory. Here's my stab at that…

You are going to play a multiplayer online game vaguely like "Mafia", but not quite as interesting. There are two teams of twenty players each. In the real world, each player is playing in a completely different building, and no one is able to communicate at all by any means outside the extremely limited interface of the game.

Each player will be assigned one of five possible colors (but there is no guarentee that all colors will be represented). Your color will be public to everyone except yourself. Throughout the game, you will see two lists: One of all the players still "on the island", and one of all who have left. Next to each player's (unique) name is her color and a symbol for her team, but no other information about her.

There is also an indicator of the number of minutes and seconds the game has been in effect, and an array of five buttons, one for each color. Your only input in the game is to press one of these buttons, which means guessing that its color is yours.

The rules are as follows: For one minute before the game "officially" starts (and before colors have been assigned), your team can interact in a chatroom to agree on a strategy. Then, the timer starts and all chat capabilities cease. From that point, the only thing you can do is press one of the buttons (you may choose not to press any). If you press a button, then as soon as the timer reaches the completion of the first minute, you are moved off the island. If your guess was correct, you earn your team one point for every minute currently on the timer. (So if you click the "purple" button right at the start of the game, and you were right, then you get one point.) If it was wrong, the game ends and your entire team loses.

After this, the timer ticks by until it reaches 2:00, and anyone who made a guess between 1:00.00 and 1:59.99 is again rewarded (this time with two points) or punished (again, with game loss). The game proceeds like this until either someone screwed up, or everyone has left the island. If either team still has anyone on the island after one hour, then that team loses (which may mean both teams losing). Otherwise, each team's scores are compared, and the lower score wins. (The game may end in a tie.)

So the question is, what strategy should you agree on beforehand, if you want to guarantee that none of your teammates will guess incorrectly? Here's my answer:

Spoiler:

I believe this is simply impossible. I'd be interested in seeing anything to contradict this.

Now, if you are willing to risk losing the game on one guess, there may be a possible strategy similar to the one used in the ten-hat version of the prisoners-and-hats puzzle. I don't know if that can be made to work when there are more than two possible colors, however. If you played this game repeatedly, there may well be some maximally efficient strategy that takes into account the expected value of making a random guess. After all, if no one ever guesses anything than you'll lose anyway, so you may as well take the risk.

The ideal strategy may be "everyone makes a random guess", but probably not. For example, I believe this is a better one: Five designated people each make a guess for one of the colors they see a non-designated teammate has. For the remaining fifteen players, the game functions like the modification described next (but there's only a 0.032% chance of getting that far).

Suppose we modify the game so that everyone learns beforehand that each team will include at least one player of each color. What is the most efficient strategy, given that you wish to get people off the island as quickly as possible? Here's my answer:

Spoiler:

I think it has been established by several people in a number of ways that no "strategy" can be more efficient than the one the islanders use in the original puzzle. Here it is as an algorithm: First, count the number of your teammates of each color. Write down a "schedule" whereby each group of that color must leave at minute N, where N is the number of teammates with that color. Pretend that each group will, in fact, leave then, and that you will simply never leave. Then, wait until a color group has failed to match your schedule — it's now Minute N and those N people are still there. This means that you are part of that group, so click the button guessing that color.

This strategy ought to work for any ratio of various colors. And because you already know that your team alone represents the whole "rainbow", you can simply ignore the other team altogether, which in turn means that there is no way for them to "confuse" you into screwing up. If both teams follow this strategy, the winner should be whichever team's ration of colors was closest to equal, 4:4:4:4:4. (In the case of identical ratios, it will of course be a tie). If your team's ratio is 15:1:1:1:1, then you will get a mere 4 points right at the start, but fourteen turns later, the fifteen other folks will each score fifteen points, leading to a final score of 229 points. Meanwhile, a team at 4:4:4:4:4 will finish with 80 points; I don't think it's possible to get fewer.

I'd be very interested if anyone could come up with a more efficient strategy. It may be the case that because this version involves two teams (or because of the nature of the scoring system), there is some clever shortcut, but I'd be surprised. Also, I wonder if there's a better overall strategy if the only knowledge you have at the start is that at least one player of each color exists, but not necessarily one on each team? In that case, it's tricky because the normal strategy would now involve "cooperating" with the other team.

[BlueSoxSWJ]

Spoiler:

Ah, I wish I'd figured out how to get email alerts on threads here, or I'd have joined the conversation about Peeling's idea; oh well. It's a neat idea but doesn't work in relation to the puzzle as originally worded.

The "aha" moment of the original puzzle is very satisfying, particularly when you see that it doesn't matter what the islanders want. Still, it's interesting to consider a variant of the problem that turns it into a game rather than a "neutral" exercise in logic, and hence involving some game theory. Here's my stab at that…

You are going to play a multiplayer online game vaguely like "Mafia", but not quite as interesting. There are two teams of twenty players each. In the real world, each player is playing in a completely different building, and no one is able to communicate at all by any means outside the extremely limited interface of the game.

Each player will be assigned one of five possible colors (but there is no guarentee that all colors will be represented). Your color will be public to everyone except yourself. Throughout the game, you will see two lists: One of all the players still "on the island", and one of all who have left. Next to each player's (unique) name is her color and a symbol for her team, but no other information about her.

There is also an indicator of the number of minutes and seconds the game has been in effect, and an array of five buttons, one for each color. Your only input in the game is to press one of these buttons, which means guessing that its color is yours.

The rules are as follows: For one minute before the game "officially" starts (and before colors have been assigned), your team can interact in a chatroom to agree on a strategy. Then, the timer starts and all chat capabilities cease. From that point, the only thing you can do is press one of the buttons (you may choose not to press any). If you press a button, then as soon as the timer reaches the completion of the first minute, you are moved off the island. If your guess was correct, you earn your team one point for every minute currently on the timer. (So if you click the "purple" button right at the start of the game, and you were right, then you get one point.) If it was wrong, the game ends and your entire team loses.

After this, the timer ticks by until it reaches 2:00, and anyone who made a guess between 1:00.00 and 1:59.99 is again rewarded (this time with two points) or punished (again, with game loss). The game proceeds like this until either someone screwed up, or everyone has left the island. If either team still has anyone on the island after one hour, then that team loses (which may mean both teams losing). Otherwise, each team's scores are compared, and the lower score wins. (The game may end in a tie.)

So the question is, what strategy should you agree on beforehand, if you want to guarantee that none of your teammates will guess incorrectly? Here's my answer:

Spoiler:

I believe this is simply impossible. I'd be interested in seeing anything to contradict this.

Now, if you are willing to risk losing the game on one guess, there may be a possible strategy similar to the one used in the ten-hat version of the prisoners-and-hats puzzle. I don't know if that can be made to work when there are more than two possible colors, however. If you played this game repeatedly, there may well be some maximally efficient strategy that takes into account the expected value of making a random guess. After all, if no one ever guesses anything than you'll lose anyway, so you may as well take the risk.

The ideal strategy may be "everyone makes a random guess", but probably not. For example, I believe this is a better one: Five designated people each make a guess for one of the colors they see a non-designated teammate has. For the remaining fifteen players, the game functions like the modification described next (but there's only a 0.032% chance of getting that far).

Suppose we modify the game so that everyone learns beforehand that each team will include at least one player of each color. What is the most efficient strategy, given that you wish to get people off the island as quickly as possible? Here's my answer:

Spoiler:

I think it has been established by several people in a number of ways that no "strategy" can be more efficient than the one the islanders use in the original puzzle. Here it is as an algorithm: First, count the number of your teammates of each color. Write down a "schedule" whereby each group of that color must leave at minute N, where N is the number of teammates with that color. Pretend that each group will, in fact, leave then, and that you will simply never leave. Then, wait until a color group has failed to match your schedule — it's now Minute N and those N people are still there. This means that you are part of that group, so click the button guessing that color.

This strategy ought to work for any ratio of various colors. And because you already know that your team alone represents the whole "rainbow", you can simply ignore the other team altogether, which in turn means that there is no way for them to "confuse" you into screwing up. If both teams follow this strategy, the winner should be whichever team's ration of colors was closest to equal, 4:4:4:4:4. (In the case of identical ratios, it will of course be a tie). If your team's ratio is 15:1:1:1:1, then you will get a mere 4 points right at the start, but fourteen turns later, the fifteen other folks will each score fifteen points, leading to a final score of 229 points. Meanwhile, a team at 4:4:4:4:4 will finish with 80 points; I don't think it's possible to get fewer.

I'd be very interested if anyone could come up with a more efficient strategy. It may be the case that because this version involves two teams (or because of the nature of the scoring system), there is some clever shortcut, but I'd be surprised. Also, I wonder if there's a better overall strategy if the only knowledge you have at the start is that at least one player of each color exists, but not necessarily one on each team? In that case, it's tricky because the normal strategy would now involve "cooperating" with the other team.

The first game should have a somewhat more decent solution ...

Spoiler:

Assign a value 1-5 to each of the 5 colors. 1 person is designated to be the signaller. That person adds the values of the other colors on his team, mods it by 5, and guesses randomly when the minute value of the timer is n. (so if he leaves at the 1 minute mark, he's signalling "0 mod 5," because he guessed between 0:00.00 and 0:59.99.) Everyone else then subtracts the (mod 5) value they see on the other 18 teammates from n (still mod 5), and has the color of his own hat, and can correctly guess in the next minute. There's an 80% chance you still lose, but a 20% chance everyone's done within 5 minutes. I'm pretty sure there's no way to keep at least one player from having to randomly guess, so I don't think you can improve on a 20% success rate.

[douglasm]

I think it has been established by several people in a number of ways that no "strategy" can be more efficient than the one the islanders use in the original puzzle.

This is not quite correct. It has been established that any such strategy requires some form of communication, most commonly in the form of an assumption of superrationality. In the original puzzle, that is banned. In your puzzle, the pre-game chat easily allows setting it up. Also, the possibility of guessing drastically alters the puzzle.

On thinking it over a little more, I suspect the original puzzle's "strategy" may indeed be the only one that is absolutely 100% guaranteed to avoid triggering an instant loss with a wrong guess, but it may be possible to greatly reduce average score with a strategy that accepts a small risk of instant loss, and the pre-game chat makes deciding on such a strategy possible.

[Lenoxus]

The first game should have a somewhat more decent solution ...

Spoiler:

Assign a value 1-5 to each of the 5 colors. 1 person is designated to be the signaller. That person adds the values of the other colors on his team, mods it by 5, and guesses randomly when the minute value of the timer is n. (so if he leaves at the 1 minute mark, he's signalling "0 mod 5," because he guessed between 0:00.00 and 0:59.99.) Everyone else then subtracts the (mod 5) value they see on the other 18 teammates from n (still mod 5), and has the color of his own hat, and can correctly guess in the next minute. There's an 80% chance you still lose, but a 20% chance everyone's done within 5 minutes. I'm pretty sure there's no way to keep at least one player from having to randomly guess, so I don't think you can improve on a 20% success rate.

Very nice!

I'm not quite following something, though…

Spoiler:

You never defined n. By "n", do you mean the same thing as the mod-5 value the signaller calculates? So N will have to be 0, 1, 2, 3, or 4. I think it makes sense now. For example, if the ratio is 2:3:7:5:3 (in ascending order for each color's number), and the signaler happens to be one of the 2s (each "worth" 1), then her calculated total is 63. 63 mod 5 is 3. The signaler leaves on Minute 3. Then the other 2 knows that he is another 2, because he calculated the same modulo. Everyone else knows that the difference between their modulo and the signaler's is accounted for by their own color. (Minus the signaler's color? Ah, but the signaler has already subtracted herself, so it all works. The signaler's a bit like a guru… heh, now I want to make a variation of the puzzle in which the guru assigns numbers to each color.)

I think I can come up with a quicker method, though. Instead of guessing randomly on Minute n, why not guess Color n on the first minute? The overall rate of success should be the same either way. (If you play the lottery every week, it makes no difference if you always write the same number or always try a new one — barring the possibility of having to share the prize, of course.) To make the game fairer, perhaps each team is permitted one or more wrong guesses, or just earns a points penalty for each wrong guess (or both).

I agree that there's no possible strategy for a team to not risk the first guess being wrong. Supposing the ratio of colors happens to be 3:9:0:8:0, and you're one of the three (but of course you don't know it). Everything you see would be consistent with 2:10:0:8:0, or 2:9:1:8:0, or 2:9:0:9:0, or 2:9:0:8:1. This state of affairs is necessarily equivalent for everyone else, and no signalling can happen until the first guess; hence, the first guess cannot have any sort of connection to one's actual color. (If you believed in the gambler's fallacy, then you might suppose it's a good idea to guess whichever color you see the least of. I'm sure the game can be set up such that that wouldn't have any advantage.)

This ties back into the original puzzle nicely, especially Objection 12, which comes up a lot (here and elsewhere) — that everyone should have left 100 days after the rules were established. Even if the islanders want to leave, the first "guesser" has absolutely nothing to go on, barring such things as sign language or knowledge of genetics. Plus, their task is by definition harder than the task in the game, because the pallet of possible colors is much more than five (although I suppose that every language has a maximum number of unique color terms).

I think it has been established by several people in a number of ways that no "strategy" can be more efficient than the one the islanders use in the original puzzle.

This is not quite correct. It has been established that any such strategy requires some form of communication, most commonly in the form of an assumption of superrationality. In the original puzzle, that is banned. In your puzzle, the pre-game chat easily allows setting it up. Also, the possibility of guessing drastically alters the puzzle.

On thinking it over a little more, I suspect the original puzzle's "strategy" may indeed be the only one that is absolutely 100% guaranteed to avoid triggering an instant loss with a wrong guess, but it may be possible to greatly reduce average score with a strategy that accepts a small risk of instant loss, and the pre-game chat makes deciding on such a strategy possible.

The earlier arguments for why the islanders can't leave sooner were made in response to people saying things like Objection 8. To summarize those arguments: Any method by which 100 blues would leave on Day L, where L < 100, would necessarily require that a hypothetical 99 blues leave on or before Day L-1, which means that a hypothetical 98 blues would leave on or before Day L-2, etc. Eventually, one reaches a point at which G blues, where G is greater than 1, would have to leave on Day 1. But that means a situation in which the entire set of blues "instantly" deduces their own eye color, which is impossible for any set greater than 1. None of the islanders has any logical reason to think that G blues could pull that off, so they won't deduce anything from that not having occurred. And of course, as has been discussed repeatedly, there can be no "common knowledge minimum" of blues other than N, where N is the current day.

Of course, the nature of superrationality is weird enough that there may be a superrational "method" I haven't considered, but I'm pretty sure that any such method boils down to "All the islanders deduce their own color on Day 1, because, being superrational, they can circularly deduce what the other islanders see." Eg, "If I were in my friend's shoes, I would see myself with brown eyes, and if he were in my shoes, he would see himself with blue eyes. Since he's superrational, he can deduce the same thing I have in reverse, therefore, the previous statement is true." Sort of like the Lorax lifting himself away…

[Lenoxus]

I might put together a 'tribute' puzzle with modified constraints where my solution is the answer, because I think it's sort of neat

On rereading this, I tried to figure out how such a puzzle might be constructed. It does look intruiging, but it still needs work.

Right at the outset, Peeling says that eir method only works if there are no unique eye colors. (It should be obvious that there is basically no way for a "singleton" to deduce her own color without the other islanders simply telling it to her. Although come to think of it, perhaps there is a method whereby those who know their own color leave after a certain number of days, in a way that "spells out" the color of the singleton in English? Huh…)

If the "no singletons" constraint is common knowledge, then, a much simpler solution should exist. If you see exactly one of a certain color, then you would know that you share it (because otherwise that color would be unique). Thus, you (and your same-colored fellow) would leave on Day 1. Then, knowing that any "doubles" would leave on Day 1, all "triples" must leave on Day 2, and thus all "quadruples" on Day 3, etc. In short, it's the same as if the Guru had said "I see at least two of the following colors…" then named each existing color.

[douglasm]

Instead of guessing randomly on Minute n, why not guess Color n on the first minute?

In order for his strategy to work, he has to communicate n to the rest of the team. Unless I'm missing something in your description of the game, which color someone guesses is not revealed to everyone, so guessing color n would not achieve that communication.

The earlier arguments for why the islanders can't leave sooner were made in response to people saying things like Objection 8. To summarize those arguments: Any method by which 100 blues would leave on Day L, where L < 100, would necessarily require that a hypothetical 99 blues leave on or before Day L-1, which means that a hypothetical 98 blues would leave on or before Day L-2, etc. Eventually, one reaches a point at which G blues, where G is greater than 1, would have to leave on Day 1. But that means a situation in which the entire set of blues "instantly" deduces their own eye color, which is impossible for any set greater than 1. None of the islanders has any logical reason to think that G blues could pull that off, so they won't deduce anything from that not having occurred. And of course, as has been discussed repeatedly, there can be no "common knowledge minimum" of blues other than N, where N is the current day.

Of course, the nature of superrationality is weird enough that there may be a superrational "method" I haven't considered, but I'm pretty sure that any such method boils down to "All the islanders deduce their own color on Day 1, because, being superrational, they can circularly deduce what the other islanders see." Eg, "If I were in my friend's shoes, I would see myself with brown eyes, and if he were in my shoes, he would see himself with blue eyes. Since he's superrational, he can deduce the same thing I have in reverse, therefore, the previous statement is true." Sort of like the Lorax lifting himself away…

Yeah, they definitely can't get a 100% proven result any faster, but the combination of both communicating strategy and being able to accept a risk of being wrong makes it possible to establish an artificial "common knowledge minimum". For example, applying this to the blue-eyes problem rather than your game, everyone could agree ahead of time to determine the highest multiple of 10 equal to or below the number of blue-eyed people they see and act as if that many days had already past. This will fail if the number of blue-eyed people is a multiple of 10, but assuming a uniform random distribution for that number there is only a 10% chance of that failure scenario happening; the other 90% of the time, the process is successfully shortened to 9 days or less no matter how many blue-eyed people there are. The solution time can be shortened further by accepting higher failure risk, or the failure risk can be reduced by accepting potentially longer solution time.

[BlueSoxSWJ]

Spoiler:

I think I can come up with a quicker method, though. Instead of guessing randomly on Minute n, why not guess Color n on the first minute? The overall rate of success should be the same either way.

Spoiler:

Actually, this can even be improved. The signaller agrees to guess n immediately. Everyone else knows the signaller's color, and thus can assume the signaller guesses correctly (since otherwise, the team has lost already). They can then assume the 19 people minus the signaller sum to n mod 5, n being the signaller's color. From there, they can figure out their own. That means, with a 20% win rate, everyone can guess immediately. It's like the "find your own name in n boxes with n/2 guesses" problem, where the optimal strategy makes either everyone fail or everyone succeed.

[Lenoxus]

Spoiler:

I think I can come up with a quicker method, though. Instead of guessing randomly on Minute n, why not guess Color n on the first minute? The overall rate of success should be the same either way.

Spoiler:

Actually, this can even be improved. The signaller agrees to guess n immediately. Everyone else knows the signaller's color, and thus can assume the signaller guesses correctly (since otherwise, the team has lost already). They can then assume the 19 people minus the signaller sum to n mod 5, n being the signaller's color. From there, they can figure out their own. That means, with a 20% win rate, everyone can guess immediately. It's like the "find your own name in n boxes with n/2 guesses" problem, where the optimal strategy makes either everyone fail or everyone succeed.

I feel like there's something wrong with this but can't put my finger on it. It's like I'm in the same position as the people who respond to the original puzzle with "But the Guru didn't tell them anything!" But indeed, it must be correct.

Spoiler:

Aha, I know what my issue is! It's that the game as I phrased it has such high stakes that if you're willing to risk one bad guess, you may as well risk a bunch more than that. (Or to be more precise, those "other" bad guesses won't ever happen because of the game ending.) It feels weird but it has to work that way. Also, I failed to clarify whether or not, in a hypothetical version where you are allowed bad guesses with a simple penalty of extra points (rather than it just ending the game), you would be able to see what the incorrect players had guessed. If you are, then my previous strategy is probably better; you first wait for the signaler's guess, be it right or wrong, then base your action on it.

[Lenoxus]

(length spoiler)

Spoiler:

Instead of guessing randomly on Minute n, why not guess Color n on the first minute?

In order for his strategy to work, he has to communicate n to the rest of the team. Unless I'm missing something in your description of the game, which color someone guesses is not revealed to everyone, so guessing color n would not achieve that communication.

The earlier arguments for why the islanders can't leave sooner were made in response to people saying things like Objection 8. To summarize those arguments: Any method by which 100 blues would leave on Day L, where L < 100, would necessarily require that a hypothetical 99 blues leave on or before Day L-1, which means that a hypothetical 98 blues would leave on or before Day L-2, etc. Eventually, one reaches a point at which G blues, where G is greater than 1, would have to leave on Day 1. But that means a situation in which the entire set of blues "instantly" deduces their own eye color, which is impossible for any set greater than 1. None of the islanders has any logical reason to think that G blues could pull that off, so they won't deduce anything from that not having occurred. And of course, as has been discussed repeatedly, there can be no "common knowledge minimum" of blues other than N, where N is the current day.

Of course, the nature of superrationality is weird enough that there may be a superrational "method" I haven't considered, but I'm pretty sure that any such method boils down to "All the islanders deduce their own color on Day 1, because, being superrational, they can circularly deduce what the other islanders see." Eg, "If I were in my friend's shoes, I would see myself with brown eyes, and if he were in my shoes, he would see himself with blue eyes. Since he's superrational, he can deduce the same thing I have in reverse, therefore, the previous statement is true." Sort of like the Lorax lifting himself away…

Yeah, they definitely can't get a 100% proven result any faster, but the combination of both communicating strategy and being able to accept a risk of being wrong makes it possible to establish an artificial "common knowledge minimum". For example, applying this to the blue-eyes problem rather than your game, everyone could agree ahead of time to determine the highest multiple of 10 equal to or below the number of blue-eyed people they see and act as if that many days had already past. This will fail if the number of blue-eyed people is a multiple of 10, but assuming a uniform random distribution for that number there is only a 10% chance of that failure scenario happening; the other 90% of the time, the process is successfully shortened to 9 days or less no matter how many blue-eyed people there are. The solution time can be shortened further by accepting higher failure risk, or the failure risk can be reduced by accepting potentially longer solution time.

Oops, I hadn't noticed this post. Yes, this is all correct, except that I'm still pretty sure that my strategy works even if incorrect guesses automatically end the game. In short: If you're going to make a random guess, you'll have a 20% chance of not losing, with the game continuing because you were right. If you instead make a "signaling guess", you also have a 20% chance of not losing, with the game continuing because you were right. Hence, you may as well go with the quicker option.

Meanwhile, I wonder if there's some sort of "perfect" multiple to agree upon beforehand, maximizing everything if the situation is considered as a game? I know that ternary is considered the most "efficient" base due to its closeness to e, but I suppose it would be too small for these purposes — or would it?

[Xias]

The interesting difference between this new game and the

Spoiler:

prisoners with hats game is that in the latter, each prisoner may only see the prisoners in front of himself. In this case, with the players able to see everyone, is there a way to create some sort of redundancy that minimizes the risk of a wrong guess?

For example, if the signaler utilizes time AND color to signal n (so the other players know that if he guesses at X time, he will guess X color) and the time for n=3 comes and goes, then every other player knows that he sees a sum of 4 mod 5; but if the signaler's hat is not the n=4 hat, then they also know that he will guess wrong and lose. If there is some way for a secondary signaler to send the primary signaler a message saying "No, your color is blue" while guessing his own color correctly, then their odds could be improved. I'm not sure how this might translate to other cases, but I do think that a team can optimize to much better han 20%, given that they can interrupt the signalling process if they know the signal will result in a fail.

[Lenoxus]

The interesting difference between this new game and the

Spoiler:

prisoners with hats game is that in the latter, each prisoner may only see the prisoners in front of himself. In this case, with the players able to see everyone, is there a way to create some sort of redundancy that minimizes the risk of a wrong guess?

For example, if the signaler utilizes time AND color to signal n (so the other players know that if he guesses at X time, he will guess X color) and the time for n=3 comes and goes, then every other player knows that he sees a sum of 4 mod 5; but if the signaler's hat is not the n=4 hat, then they also know that he will guess wrong and lose. If there is some way for a secondary signaler to send the primary signaler a message saying "No, your color is blue" while guessing his own color correctly, then their odds could be improved. I'm not sure how this might translate to other cases, but I do think that a team can optimize to much better han 20%, given that they can interrupt the signalling process if they know the signal will result in a fail.

The problem there is that

Spoiler:

guessing your color is the only way to signal, and hence the first guess, whether done by a primary, secondary, or tertiary signaler, will always have to be totally uninformed (barring a Guru-like source of information). Thus, 20% is the best success rate for which one can hope; it's the hoop through which any team has to jump.

The very fact that even 20% is possible right off the bat, no matter the distribution of colors, somewhat blows my mind, but just as with the original puzzle, it feels easier to understand if I scale it down. When I consider the situation with just two colors, there's a definite logic in the maximum rate of "everyone gets it right" being 50% off the bat; the trick is basically that they collectively assume the number of each color is odd, and (given that the team has an even numbers of members) there's a 50% chance of that being the case. (Or they do the same with even, as happens to be true in the original.) But when it comes to three colors having a 33% chance, my brain begins to hurt.

[Xias]

The interesting difference between this new game and the

Spoiler:

prisoners with hats game is that in the latter, each prisoner may only see the prisoners in front of himself. In this case, with the players able to see everyone, is there a way to create some sort of redundancy that minimizes the risk of a wrong guess?

For example, if the signaler utilizes time AND color to signal n (so the other players know that if he guesses at X time, he will guess X color) and the time for n=3 comes and goes, then every other player knows that he sees a sum of 4 mod 5; but if the signaler's hat is not the n=4 hat, then they also know that he will guess wrong and lose. If there is some way for a secondary signaler to send the primary signaler a message saying "No, your color is blue" while guessing his own color correctly, then their odds could be improved. I'm not sure how this might translate to other cases, but I do think that a team can optimize to much better han 20%, given that they can interrupt the signalling process if they know the signal will result in a fail.

The problem there is that

Spoiler:

guessing your color is the only way to signal, and hence the first guess, whether done by a primary, secondary, or tertiary signaler, will always have to be totally uninformed (barring a Guru-like source of information).

No. Remember the puzzle this thread is about? Not guessing can also transmit information.

Consider two-color case.

Spoiler:

Normally in this problem they are in a line and can only see those in front of them, and they are asked in order without the opportunity to speak when it is not their guess. The additional rules throw that out the window.

In the two-color case, then say white=0, black=1. Person A is the signaler, and at 30 seconds he will press white if the sum he sees is 0, and at 60 seconds he will press the black if the sum he sees is 1.

Say his color is white. Person B waits to see if at 30 seconds, A presses white. If A does, then A has successfully transmitted the information and guessed his own color. They all "win". If A does not guess white at 30 seconds, then B knows that A does not see a modular sum of 0, and will guess black at 60 seconds. Person A has already transferred the sum information, but his guess will be wrong. Person B can signal back to A by guessing his own color at 45 seconds, telling A that his color is white. They all "win." They can win with 100% probability if As color is white.

If As color is black, then even with no failsafe, they can win with 50% probability. Overall, their odds must be equal to or greater than 75%. A straight mod sum strategy that gives 50% is far from optimal.

Having just one failsafe is far from optimal as well; If As color is black, then B would not want to let the clock reach 30. So, if B sees a modular sum of 0, he will guess white at 10 seconds, otherwise he will guess black at 20 seconds. If his hat is white and he sees a sum of 0, they all win. If his hat is white and he sees a sum of 1, Person C (who sees that A is black and B is white and knows that B sees a sum of 1) will guess his own color correctly at 15 seconds, signalling to A and B that they are black and white, respectively. If A is black and B is white, they win with 100% probability. If the [A,B]=[black, black] case wins with 50% probability, then we have a probability of winning of 87.5%; much greater than 50%.

Here's a timeline of how it would go down:
0:10 - B guess white if B_sum=0 and A is black. Lose if B is black.
0:15 - C guess C_sum+1 if B is white and A is black and B has not guessed. Win.
0:20 - B guess black if B_sum=1 and A is black and C has not guessed. Win.
0:30 - A guess white if A_sum=0 and B and C have not guessed. Win.
0:45 - B guess B_sum if A is white and A,B,C have not guessed. Win.

There's some redundancy, so A can never actually guess black at 60 seconds. But after any of these cases, all of the others know what at least one sum is, and can find their own color. The division and delegation can continue indefinitely to approach 100% success. I think this can translate to the 5-color case.

Edit: I just realized that I hardly ever solve these things. I usually just think about them for a long time until I discover something interesting that might lead to a better answer and then I post it and forget about it. Maybe I'll actually sit down and try to solve this one.

[sam_i_am]

Now, What If all the Islanders imagined that the guru said that he can see someone with brown eyes simultaneously, not because of any hallucination, but because of a logical device so that they can leave the island if their eyes are blue OR if their eyes are brown, and followed the exact same induction

Now put yourself in the mind of an islander(you don't know whether your eyes are blue, brown, or red), and you followed the above logic.

Can you imagine a scenario where you would attempt to leave the island and be wrong?

[t1mm01994]

Erm, I have trouble making sense out of that. Assuming the guru said "I see someone with blue eyes and someone with brown eyes" both counters start running simultaneously and all blue and all brown eyed people will leave. No islanders can ever be wrong, that's what "perfect logician" gets done.

[sam_i_am]

Erm, I have trouble making sense out of that. Assuming the guru said "I see someone with blue eyes and someone with brown eyes" both counters start running simultaneously and all blue and all brown eyed people will leave. No islanders can ever be wrong, that's what "perfect logician" gets done.

This changes the problem a bit. Let's call it the Blue Eyes "cheater" problem. all the people on the island cheat, and use the same process of blue eyes, for every other eye color that they see a lot of (more than 10) for quantification's sake.

From the perspective of an islander(doesn't know the own color of their eyes) does anyone have a chance of being wrong?

[douglasm]

From the perspective of an islander(doesn't know the own color of their eyes) does anyone have a chance of being wrong?

In this specific situation, no. The islanders are, however, no longer perfect logicians and there are scenarios where many of them would be wrong.

[sam_i_am]

From the perspective of an islander(doesn't know the own color of their eyes) does anyone have a chance of being wrong?

In this specific situation, no. The islanders are, however, no longer perfect logicians and there are scenarios where many of them would be wrong.

not just in this specific situation, but also the situation where one islander instead has red eyes, or the situation where there are 101 of one color of eyes, and 99 of the other. will any islander guess wrong?

Edit: I found it out. If you have red eyes, than there are 100 people whom see 99 of each, and they are all at danger of mis-picking, yet I feel that the same holds true for if the guru sees both blue and brown eyes.

[Gwydion]

From the perspective of an islander(doesn't know the own color of their eyes) does anyone have a chance of being wrong?

In this specific situation, no. The islanders are, however, no longer perfect logicians and there are scenarios where many of them would be wrong.

not just in this specific situation, but also the situation where one islander instead has red eyes, or the situation where there are 101 of one color of eyes, and 99 of the other. will any islander guess wrong?

Edit: I found it out. If you have red eyes, than there are 100 people whom see 99 of each, and they are all at danger of mis-picking, yet I feel that the same holds true for if the guru sees both blue and brown eyes.

This last part confuses me, so I'll try to restate. Are you saying there are 100 brown, 99 blue, and 1 red (you)? In that case, the blue-eyed islanders will see 98 pairs of blue eyes and 100 pairs of brown eyes, and they leave on day 99 knowing their eyes must be blue. The brown-eyed islanders see 99 pairs of blue eyes and 99 pairs of brown eyes, and also see all of the blue-eyed islanders leave day 99. They'll correctly deduce that they all have brown eyes and leave day 100, as expected. You, on the other hand, will see 99 pairs of blue eyes leave day 99, and 100 pairs of brown eyes leave day 100, and will stay forever. Nobody was wrong, right?

[sam_i_am]

From the perspective of an islander(doesn't know the own color of their eyes) does anyone have a chance of being wrong?

In this specific situation, no. The islanders are, however, no longer perfect logicians and there are scenarios where many of them would be wrong.

not just in this specific situation, but also the situation where one islander instead has red eyes, or the situation where there are 101 of one color of eyes, and 99 of the other. will any islander guess wrong?

Edit: I found it out. If you have red eyes, than there are 100 people whom see 99 of each, and they are all at danger of mis-picking, yet I feel that the same holds true for if the guru sees both blue and brown eyes.

This last part confuses me, so I'll try to restate. Are you saying there are 100 brown, 99 blue, and 1 red (you)? In that case, the blue-eyed islanders will see 98 pairs of blue eyes and 100 pairs of brown eyes, and they leave on day 99 knowing their eyes must be blue. The brown-eyed islanders see 99 pairs of blue eyes and 99 pairs of brown eyes, and also see all of the blue-eyed islanders leave day 99. They'll correctly deduce that they all have brown eyes and leave day 100, as expected. You, on the other hand, will see 99 pairs of blue eyes leave day 99, and 100 pairs of brown eyes leave day 100, and will stay forever. Nobody was wrong, right?

Yeah I suppose that's right.

[kousi]

Alright I've posted this to reddit a couple times with no responses, hoping you guys can shine some light on it:

Problem:
http://xkcd.com/blue_eyes.html

Accepted solution:
http://xkcd.com/solution.html

Suggested optimization:

From a blue:

I see 99 blues, believing I could be the 100th blue
I know the blues see 98 or 99 blues themselves.
Therefore they believe the minimum of blues is 98.
We treat night 1 as night 99, we expect those who see 98 blue eyes to leave
No one leaves, we now know the blues also see 99 blue eyes.
We treat night 2 as night 100, we expect who see 99 blue eyes to leave
I leave, all the blues leave.

From a brown/green:

I see 100 blues believing I could be the 101st blue
I know they see 99 or 100 blues themselves.
I know they believe the other blues see 98 or 99 blues
Therefore they believe the minimum of blues is 98.
We treat night 1 as night 99, we expect those who see 98 blue eyes to leave
I know that no one will leave, but I know that they don't know
No one leaves, we now know everyone sees 99 blue eyes or more
We treat night 2 as night 100, we expect who see 99 blue eyes to leave
I know this is the minimum, but I could be the lucky 101st
All the blues leave.

I cry because I was going to leave the next night if they didn't leave.

[csanders]

That can't work because you have different logic in the "From a blue" and "From a brown/green" sections. The blues see N=99 blue eyed people and decide to start counting at N. The browns see N=100 blue eyed people and somehow decide to start counting at N-1. How does that work if they don't know their eye color? How do they decide which set of logic to follow?

For example, if there's a person on an island who sees 47 blue eyes, and wants to use your optimization, what number do they start counting at?

[Xias]

Alright I've posted this to reddit a couple times with no responses, hoping you guys can shine some light on it:

Problem:
http://xkcd.com/blue_eyes.html

Accepted solution:
http://xkcd.com/solution.html

Suggested optimization:

From a blue:

I see 99 blues, believing I could be the 100th blue
I know the blues see 98 or 99 blues themselves.
Therefore they believe the minimum of blues is 98.
We treat night 1 as night 99, we expect those who see 98 blue eyes to leave
No one leaves, we now know the blues also see 99 blue eyes.
We treat night 2 as night 100, we expect who see 99 blue eyes to leave
I leave, all the blues leave.

From a brown/green:

I see 100 blues believing I could be the 101st blue
I know they see 99 or 100 blues themselves.
I know they believe the other blues see 98 or 99 blues
Therefore they believe the minimum of blues is 98.
We treat night 1 as night 99, we expect those who see 98 blue eyes to leave
I know that no one will leave, but I know that they don't know
No one leaves, we now know everyone sees 99 blue eyes or more
We treat night 2 as night 100, we expect who see 99 blue eyes to leave
I know this is the minimum, but I could be the lucky 101st
All the blues leave.

I cry because I was going to leave the next night if they didn't leave.

Objection 8 seems to fit here.

To clarify what csanders is saying, both the blue and brown eyed islanders start counting the first day as 99; why is that? If the blue-eyed islanders count day 1 as 99, wouldn't the brown-eyed islanders count day 1 as 100, and believe they were blue-eyed on day 2?

[Lenoxus]

The specific problem is this. In the brown/green thought process, you have the following step:

I know they believe the other blues see 98 or 99 blues.

But there's no equivalent step in the blue thought process! In order to avoid that step, a blue would have to know more than he can know. If we insert that step, then we get:

From a blue:

I see 99 blues, believing I could be the 100th blue
I know the blues see 98 or 99 blues themselves.
I know they believe the other blues see 97 or 98 blues.
Therefore they believe the minimum of blues is 97.
We treat night 1 as night 98, we expect those who see 97 blue eyes to leave
I know that no one will leave, but I know that they don't know
No one leaves, we now know the blues also see 98 blue eyes.
We treat night 2 as night 99, we expect those who see 98 blue eyes to leave.
I know this is the minimum, but I could be the lucky 100th
No one leaves.
The next day, everyone leaves. I guess someone secretly told all the browns their color?
On the boat, all the brown-eyed people tell me how they deduced their eyes were blue. I cry.

[skullturf]

I must confess that I'm not a big fan of using words like "optimization" or "strategy" or "treat night 1 as night 99" when talking about this puzzle.

The islanders aren't "trying" to leave the island, and they're not trying not to leave the island. I'm pretty sure the original statement of the puzzle says nothing about whether or not leaving the island is considered desirable.

And the islanders aren't especially "trying" to guess anyone's eye color "early". They are merely making deductions from what they know; that's all.

If I'm insisting on strict definitions, I'm not even sure what "treat night 1 as night 99" means. They can't lie; they know night 1 isn't night 99, but also, how would they know to "decide" to treat night 1 as a certain other night?

The thing is, the islanders are not going to arbitrarily adopt some kind of ad hoc strategy that will "help" them figure things out "early". They merely make deductions from what they know. But they're perfect logicians, so they make all logically permissible deductions from everything they know.

They start out knowing things like "There are at least 99 blue-eyed people" and "Alice knows there are at least 98 blue-eyed people", and then after the guru's announcement, the islanders then know things like "Everyone knows that everyone knows that everyone knows that [ridiculous number of times] there is at least one blue-eyed person" and then, after the first night, they know things like "Nobody left on the first night", and so on.

The islanders merely make deductions from what they know. They aren't engaging in a strategy; they're just perfect logicians who can't help but just instantly "see" all logical consequences of the set of facts they know. They aren't "trying" to do anything.

[Lenoxus]

The interesting difference between this new game and the

Spoiler:

prisoners with hats game is that in the latter, each prisoner may only see the prisoners in front of himself. In this case, with the players able to see everyone, is there a way to create some sort of redundancy that minimizes the risk of a wrong guess?

For example, if the signaler utilizes time AND color to signal n (so the other players know that if he guesses at X time, he will guess X color) and the time for n=3 comes and goes, then every other player knows that he sees a sum of 4 mod 5; but if the signaler's hat is not the n=4 hat, then they also know that he will guess wrong and lose. If there is some way for a secondary signaler to send the primary signaler a message saying "No, your color is blue" while guessing his own color correctly, then their odds could be improved. I'm not sure how this might translate to other cases, but I do think that a team can optimize to much better han 20%, given that they can interrupt the signalling process if they know the signal will result in a fail.

The problem there is that

Spoiler:

guessing your color is the only way to signal, and hence the first guess, whether done by a primary, secondary, or tertiary signaler, will always have to be totally uninformed (barring a Guru-like source of information).

No. Remember the puzzle this thread is about? Not guessing can also transmit information.

Consider two-color case.

Spoiler:

Normally in this problem they are in a line and can only see those in front of them, and they are asked in order without the opportunity to speak when it is not their guess. The additional rules throw that out the window.

In the two-color case, then say white=0, black=1. Person A is the signaler, and at 30 seconds he will press white if the sum he sees is 0, and at 60 seconds he will press the black if the sum he sees is 1.

Say his color is white. Person B waits to see if at 30 seconds, A presses white. If A does, then A has successfully transmitted the information and guessed his own color. They all "win". If A does not guess white at 30 seconds, then B knows that A does not see a modular sum of 0, and will guess black at 60 seconds. Person A has already transferred the sum information, but his guess will be wrong. Person B can signal back to A by guessing his own color at 45 seconds, telling A that his color is white. They all "win." They can win with 100% probability if As color is white.

If As color is black, then even with no failsafe, they can win with 50% probability. Overall, their odds must be equal to or greater than 75%. A straight mod sum strategy that gives 50% is far from optimal.

Having just one failsafe is far from optimal as well; If As color is black, then B would not want to let the clock reach 30. So, if B sees a modular sum of 0, he will guess white at 10 seconds, otherwise he will guess black at 20 seconds. If his hat is white and he sees a sum of 0, they all win. If his hat is white and he sees a sum of 1, Person C (who sees that A is black and B is white and knows that B sees a sum of 1) will guess his own color correctly at 15 seconds, signalling to A and B that they are black and white, respectively. If A is black and B is white, they win with 100% probability. If the [A,B]=[black, black] case wins with 50% probability, then we have a probability of winning of 87.5%; much greater than 50%.

Here's a timeline of how it would go down:
0:10 - B guess white if B_sum=0 and A is black. Lose if B is black.
0:15 - C guess C_sum+1 if B is white and A is black and B has not guessed. Win.
0:20 - B guess black if B_sum=1 and A is black and C has not guessed. Win.
0:30 - A guess white if A_sum=0 and B and C have not guessed. Win.
0:45 - B guess B_sum if A is white and A,B,C have not guessed. Win.

There's some redundancy, so A can never actually guess black at 60 seconds. But after any of these cases, all of the others know what at least one sum is, and can find their own color. The division and delegation can continue indefinitely to approach 100% success. I think this can translate to the 5-color case.

Edit: I just realized that I hardly ever solve these things. I usually just think about them for a long time until I discover something interesting that might lead to a better answer and then I post it and forget about it. Maybe I'll actually sit down and try to solve this one.

Half a year later, I realize I never responded to this. Anyway, it sounds correct to me. I hadn't considered "time of guess in seconds" to be public knowledge in the game as I imagined it; my assumption was that everyone is in the dark for the full minute, and only discovers at the start of the next minute what guesses were made. (That's what it can be like to be a "townie" in online mafia -- during the night phase, you don't have any sense of what's going on, and then in the day phase you see reports about who was killed off, and so forth.)

I really like the fact that just by adding a seconds parameter, success can be arbitrarily close to 100%. That binary situation -- guessing or not guessing -- is all you need.