Here are some variants to the Blue Eyes puzzle. All the rules are the same, but there are differences in (a) the number of people of different eye colors and (b) the oracle's statement. It is not necessary that everyone leaves - there could be a deadlock as well.
Variant 1: (a) 50 blue, 50 not blue (b) "At least one, but not all of you are blue-eyed."
Variant 2: (a) 100 blue, 50 not blue (b) "There are more blue-eyed people than those who are not."
Variant 3: (a) 100 blue (b) "At least 10 of you are blue-eyed."
Variant 4: (a) 50 blue, 50 not blue (b) "There are at least 10, but not more than 75 blue-eyed people."
Answer
Variant 1:
The oracle saying "not everyone has blue eyes" does not add any information here. Consider the case where there are only two people on the island, one of whom has blue eyes and the other having brown eyes. Being told that "not everyone has blue eyes" gives the blue-eyed person no information - seeing a brown-eyed person, the statement could have been trivial (i.e "not everyone has blue eyes because nobody has blue eyes") or not, and the blue-eyed person has no way to tell the difference. The brown-eyed person, seeing a blue-eyed person, does get some information about their eye color - it is not blue. Because they still do not know what color their eyes are (only a little bit about what they aren't), this statement, by itself, is not enough to cause anyone to leave.
With the first part of the statement being "At least one person has blue eyes", the second half of the statement is redundant. Following the same logic as in the original problem, all the blue-eyed people will leave on
day 50
. Then everyone who remains will know that they do not have blue eyes, therefore not everyone had blue eyes. Again, all of the people who remain will now have no clue as to their eye color other than that it is not blue.
Variant 2:
"There are more blue-eyed people than those who are not."
Consider the case of $N+1$ blue-eyed people and $N$ non-blue-eyed people (we'll say they're all green for simplicity). On the first day, each B sees $N$ B's and $N$ G's. In order for there to be more B's, they must be B. So on day 1, all blue-eyed people leave. If there are $N+2$ B's and $N$ G's, each blue-eyed person sees $N+1$ B's and $N$ G's. They must have blue eyes for there to be a greater number of blues than greens, so again all B's leave on day 1.
Now consider larger gaps - $N+3$ B's and $N$ G's. Each B cannot tell the difference between the real scenario and $N+2$ B's and $N+1$ G's. Same with $N+4$ vs $N$ not being distinguishable from $N+3$ and $N+1$. However, when nobody leaves the first day, the other possibilities are removed, so all the blue-eyed people leave on day 2.
So for both odd and even numbers of total people, the induction able to start with the halfway point being considered day 0. With 150 people, if there were 76 B's they would leave on day 1. If there were 77 B's, they would leave on day 2.
Following this pattern, all of the blue-eyed people will leave on
day 25
Variant 3:
"At least 10 of you are blue-eyed."
This simply starts off the induction a few steps down the line. 10 B's would leave on day 1, 11 B's would leave on day 2, ... so 100 B's (everyone) will leave on
day 91
Variant 4:
"There at least 10, but not more than 75 blue-eyed people."
As with variant 4, this starts off the induction a few steps down the line so all the blue-eyed people will leave no later than day 41. However, what about the second half of the statement?
Consider the case where we have 1 B and 1 G, and the oracle says "There is not more than 1 blue-eyed person". This statement could be said even if there were not any blue-eyed people, so the blue-eyed person does not know if their eyes are blue or not. The green-eyed person sees blue eyes and so knows that they do not have blue eyes. Again, knowing a single color that their eyes are not not does not reveal what color they are. If there were 2 G's and the oracle said "There is not more than 1 blue-eyed person", neither would know any new information about their eyes. If there are 2 G's and 1 B when the oracle says "There is not more than 1 blue-eyed person", the two G's both know their eyes are not blue, while the B knows nothing new.
If there are 2 G's and 1 B and the oracle says "There are not more than 2 blue-eyed people", nobody will know anything new. The oracle could say that for 2 B's and 1 G, 1 B and 2 G's, or 0 B's and 3 G's. They will each know that everyone else knows that there are not 3 B's, but the only information that can give anyone is what color their eyes are not, which is not actionable. Therefore nobody else's actions (or lack thereof) will give them any information to further distinguish between the possibilities.
So the second half the oracle's statement in this variant does not help give any information, so all of the blue-eyed people will leave on
day 41
No comments:
Post a Comment