Tuesday, July 24, 2018

logical deduction - Green Eyed Oracle Variant - Not a Multiple of 17


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 L1,L2,,Ln. 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 L1 knows that if his own eyes are brown, then L2 would know the number of blue-eyed logicians is 0 or 1, and the oracle's statement would tell L2 his own eye colour on the first day. When L2 doesn't leave on the first day, L1 knows his own eyes must be blue. L2 can argue similarly, so they both leave on the second day.


If n=3, the L3 knows that if his own eyes are brown, then L1 and L2 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 L3 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 n1 is any other multiple of 17), they all leave on the first day because they knew beforehand that there are either n or n1 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 L87 knows that if his own eyes are brown, then L1,,L86 argue exactly as in the n=86 case and leave on the first day. They don't, so L87 leaves on the second day. By symmetry, everyone does.


In general, everyone leaves on the (n17k)th day if $17k

No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...