$100$ perfect logicians have been gathered on an island. It is common knowledge that logicians always have blue or brown eyes, though on this island, all eyes are blue. However, there are no reflective surfaces, and talking about eye color is forbidden; in short, each logician knows everyone else's eye color, but not their own.
One Sunday afternoon, a green-eyed oracle visits the island, and makes the following decree, loud enough for all to hear:
The number of blue eyed logicians on this island is not a multiple of $17$.
(The multiples of $17$ up to $100$ are $0,17,34,51,68,85$).
It is common knowledge that the oracle knows all, and never lies. Starting that on that Sunday midnight, and every midnight thereafter, a ferry comes to take away anyone who knows their own eye color. The question is:
Will the logicians ever leave, and if so, on what day?
Please hide any guesses/solutions with spoilers, for the benefit of other solvers.
Remarks: It seems like the oracle has said nothing new, since everyone already knew the number of blue-eyed logicians was either $99$ or $100$, and $17$ divides neither of these. Anyone familiar with these sorts of puzzles will confirm that, counterintuitively, statements like this have some content, which can be enough do allow the logicians to deduce their freedom.
Edit I changed the number the oracle says, since I think it was originally too easy.
Answer
The answer is
all the logicians leave on the 15th day.
Proof
Let's generalise the problem and say there are $n$ logicians on the island, all with blue eyes. Call them $L_1,L_2,\dots,L_n$. So our specific problem is where $n=100$.
If $n=1$, then the single logician knows from the oracle's statement that the number of blue-eyed logicians on the island isn't $0$, so it must be $1$; he leaves on the first day.
If $n=2$, then $L_1$ knows that if his own eyes are brown, then $L_2$ would know the number of blue-eyed logicians is $0$ or $1$, and the oracle's statement would tell $L_2$ his own eye colour on the first day. When $L_2$ doesn't leave on the first day, $L_1$ knows his own eyes must be blue. $L_2$ can argue similarly, so they both leave on the second day.
If $n=3$, the $L_3$ knows that if his own eyes are brown, then $L_1$ and $L_2$ would argue exactly as above (each of them knows there are either $1$ or $2$ blue-eyed logicians, as in the previous scenario) and leave on the second day. They don't, so $L_3$ leaves on the third day. By symmetry, they all do.
The same argument goes on until $n=17$. Note that this case is impossible since the oracle always tells the truth. However this makes the case $n=18$ interesting. In this case (or if $n-1$ is any other multiple of $17$), they all leave on the first day because they knew beforehand that there are either $n$ or $n-1$ blue-eyed logicians on the island, and the oracle's statement tells them immediately which is correct. So let's skip ahead to $n=86$.
If $n=86$, then each logician knows beforehand that there are either $85$ or $86$ blue-eyed logicians on the island, so the oracle's answer tells them which immediately, and they all leave on the first day.
If $n=87$, then $L_{87}$ knows that if his own eyes are brown, then $L_1,\dots,L_{86}$ argue exactly as in the $n=86$ case and leave on the first day. They don't, so $L_87$ leaves on the second day. By symmetry, everyone does.
In general, everyone leaves on the $(n-17k)$th day if $17k
No comments:
Post a Comment