7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ " though on this island, all eyes are blue " and 0 is not multiple of 17 ? $\endgroup$ – user2408578 Apr 14 '15 at 8:12
  • $\begingroup$ @user2408578 0 is a multiple of 17. The oracle's statement is consistent with reality; there are 100 blue-eyed logicians, and 100 is not a multiple of 17. $\endgroup$ – Mike Earnest Apr 14 '15 at 8:17
  • $\begingroup$ Nor is 100 a multiple of 7, so why is 7 easier? $\endgroup$ – Vincent Apr 14 '15 at 9:58
  • $\begingroup$ @VincentAdvocaat If you replace 17 with 7, everyone leaves the next day, and you can give a quick proof of why. With 17, the reasoning is more complicated. $\endgroup$ – Mike Earnest Apr 14 '15 at 16:17
  • $\begingroup$ @MikeEarnest look at the comment i made on rand al'thor's answer. I just don't quite understand it. Also, does this go for any number less than the actual number of blue eyed persons or only for prime numbers, i take it you took 2 primes by coincidence but seeing as i can't figure out why the statement from the oracle works i might as well be mistaken about that, haha $\endgroup$ – Vincent Apr 14 '15 at 16:32
7
$\begingroup$

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<n<17k+17$ (and on the $1$st day if $n=17k$). When $n=100$, we have $k=5$ and so everyone leaves on the $15$th day.

$\endgroup$
  • $\begingroup$ very fast man.i forgot to see there is answer.:( $\endgroup$ – user2408578 Apr 14 '15 at 10:10
  • $\begingroup$ Is the whole "explanation to come" thing acceptable in this community? It is a far cry from giving a concise answer and then elaborating further. $\endgroup$ – kaine Apr 14 '15 at 10:11
  • 1
    $\begingroup$ @d'alar'cop I've heard of it, yes. Actually it was you who told me this is done on SO ("one can tell I was trained in Stack Overflow :p", but I can't find the link). $\endgroup$ – Rand al'Thor Apr 14 '15 at 11:52
  • 1
    $\begingroup$ Your case for 1, 2, and 3 look understandable to me, but I'm afraid I don't follow your argument for $n = 4$. All of the logicians see three pairs of blue eyes. By this, they each know that the other logicians see at least two pairs of blue eyes. Since neither 2 nor 3 is divisible by 17, the logicians cannot deduce their own eye colour. It could be brown today, just like it could be brown tomorrow. I don't see how a new day affects the logician's understanding in this case. $\endgroup$ – Ian MacDonald Apr 14 '15 at 12:47
  • 1
    $\begingroup$ @VincentAdvocaat the oracles statement does imply that there is at least one blue logician, even when $n=1$, because 0 is a multiple of 17, and the oracle says there aren't a multiple of 17 blue eyed logicians, so there can't be zero of them $\endgroup$ – Mike Earnest Apr 14 '15 at 16:47
0
$\begingroup$

rand al'thor's answer provides a proof for the "maximum" minimum number of days required for all the blue-eyed logicians to determine their own eye color. It is the most common "correct" answer, and it works for "common" logicians.

But, these are perfect logicians, so another point of information can be included as common knowledge, which drops the earliest day all the blue-eyed logicians can leave to

the 4th (Wednesday) if there are at least two eye colors, and the 3rd (Tuesday) if everyone has the same eye color.

Explanation

Every logician knows how many logicians there are, and every logician knows that every other logician knows this. (obvious)

If the number of blue-eyed logicians is N, then every logician knows that there are at least N-1 blue-eyed logicians (not knowing whether each himself has blue eyes). Furthermore, every logician knows that every blue-eyed logician knows that there are at least N-2 blue-eyed logicians. (Thus, every situation where the number of blue-eyed logicians is less than N-2 can be immediately eliminated from consideration.)

Thus, the first day after the pronouncement, no logicians will leave, because every logician knows that there are more than N-2 blue-eyed logicians, but suspects that a blue-eyed logician might only see N-2 other blue-eyed logicians. (It might be worth stating that none of the logicians expects any of them to leave the first night.)

The second day, the logicians know that no logicians left, and so learn that no logician can see only N-2 blue-eyed logicians. Each still doesn't know whether he himself has blue eyes, but he knows that if there are only N-1 blue-eyed logicians, that they would know this today and leave tonight. (Each logician expects that all the other logicians will leave tonight if he himself does not have blue eyes.)

The third day, all the logicians know that none of the other logicians left on the second night, so must conclude that all the logicians, including himself, have blue eyes. All the logicians will leave on the third night.

The special cases with N=1 or N=2 (or either N-1 or N-2 is a multiple of 17) blue-eyed logicians means the exodus of the logician(s) will be on the 1st or 2nd day, since N(mod 17)-2 and N(mod 17)-1 cannot be negative.

I have given a more extensive answer here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.