Island of the Variously Tall Logicians
Posted by Rob Herman at August 10th, 2006
As promised, an extension of the Island of the Logicians riddle. Intrepid reader John Rhoadhouse and I seem to have a solution (the credit is mostly his) but are not 100% convinced. So here you go.
As before, there are 100 logicians on an island. This time, instead of distinctively colored eyes, each logician has a dot, red or blue, on top of their head. Furthermore, the logicians are all different heights. Each logician can see the dot on the top of every shorter logician’s head, but not the dot on any taller logician.
As in the previous riddle, every night at midnight, a ferry comes and takes away any logician that knows the color of his or her own dot; and logicians don’t talk about the color of one another’s dots.
One day, in a crash of lightning, a stone tablet appears. This time it has two statements. Both are true. The first one is: “This information will enable all of you to leave the island.”
The riddle is, if you can, to find a second true statement that enables all of the logicians to leave the island, but not all on the first night. You may distribute the red and blue dots however you wish. If this cannot be done, and John and I believe it cannot, explain why.
If you’re having a tough time trying to wrap your head around this, you’re not alone. Consider the statement: “Exactly one of you has a red dot.” What you will discover is that if both statements on the tablet are to be true, only the shortest logician is allowed to have a red dot! Since the logicians know this, they are all able to leave the first night.
It’s maddeningly tempting to forget about the first statement on the tablet, especially since it’s easy to come up with configuration/statement pairs that allow everyone to leave the island.
This seems to be related to the paradox of a professor who promised to give his students a surprise quiz at some point the following week. The students’ reasoning goes like this:
- The quiz can’t be on Friday, because if Thursday rolled around and the quiz still hadn’t been given yet, it wouldn’t be a surprise.
- So the quiz can’t be on Thursday; because if Wednesday rolled around and the quiz still hadn’t been given, since Friday has been eliminated, the test would have to be on Thursday. But then the quiz wouldn’t be a surprise.
- So the quiz can’t be on Wednesday, because if Tuesday rolled around and the quiz still hadn’t been given, it would have to be Wednesday because Thursday and Friday are out. But then the quiz wouldn’t be a surprise.
- …And so on for Tuesday and Monday, and the students determine that a surprise quiz cannot be given at all.
This paradox derives from an unusually literal meaning of the idea of “surprise,” but has the same idea that the advance knowledge that something will happen affects its ability to happen in that way.
Actually with an even numbered population the statement “Exactly one of you has a red dot.” will not get everyone off the island even if the shortest person has the red dot.
I think it would work. Everyone but the shortest would know that they must have a blue dot. The shortest person then knows he has the red dot, because no other placement would allow the other 99 to leave. Shruti and I believe that this will work up to the lone red dot being on the 98th shortest (third tallest).
John maybe you can explian why it matters if there is an even or odd number.
In fact I think this will work for situations where
x=exact number of red dots AND
no red dots appear in the X+1 tallest positions AND
the process will take X+1 nights
I have only reasoned this for small numbers of X. I am pretty sure it will not work with a 50/50 split. Definitely not at any random distribution yet.
ADDENDUM
Also all dots must have X+1 spaces in between them. This limits the scenarios even further to X(X+1)
Ok, in actually a similar manner to the solution for the similarly heighted logicians, I wonder why a statement as to the number of red-dotted persons does not allow everyone to leave after R+1 nights, as long as the two tallest have blue dots.
Night 1, all the blues who can see R red dots leave.
Night 2, having noted a group of more than 1 person leave above him, the tallest red can deduce that they all could see R reds, and seeing only R-1, he leaves. Also, the next group of blues can deduce that the tallest person remaining must have a red dot, so they all can also leave.
Similarly, through night R+1, whereupon everyone remaining knows that the tallest person has a red dot and they all have blue.
The fact that the following group of blue dots can leave along with the top red was tying me up, but as long as they can fully trust the reasoning skills of the others, which has been assumed previously, it seems to work. Not sure if I’m missing something, of course.
Both statements have to be true thus there can only be one red dot (assuming the second statement is the one Master Author Rob suggested). Let us look at the case of population equal to four and population equal to five.
First population (n) = 4
There are four different configurations listing people in order of tallest to shortest
1)RBBB
2)BRBB
3)BBRB
4)BBBR
Now let us assume for the moment that the logicians do not all know they are geting off of the island and look at each case
1) night 1: The tallest sees no red dots and knows he has the red dot so he leaves
night 2-forever: Since the tallest could have seen a red dot on the second tallest and known he has a blue dot and left the second tallest does not know if he has a blue dot or a red dot and neither does anyone shorter than the second tallest. Therefore no one else can leave
2)night 1: The tallest sees a red dot on the second tallest and knows he has a blue dot since there is exactly one red dot so he leaves
night 2-forever: Since the tallest could have seen a blue dot on the second tallest and known he has a red dot and left the second tallest does not know if he has a blue dot or a red dot and neither does anyone shorter than the second tallest. Therefore no one else can leave
3) night 1: the tallest and second tallest both see a red dot on the third tallest so they both know that they have blue dots and leave the first night
night 2: since the second tallest left he must have seen a red dot and since the third tallest didn’t leave it means he did not see a red dot which means that the third tallest has a red dot and the fourth tallest has a blue dot so they both leave.
4) night 1: All but the shortest leave since they see the red dot on the shortest
night 2: The shortest person knows that everyone taller than him saw a red dot so it must be his since he is the shortest. So he leaves.
Now we remember that they know all of them must be able to leave the island thus they know that case 1 and case 2 are impossible since not everyone can leave the island in that case. Using this knowledge they all deduce that the tallest and second tallest must have blue dots since case 3 and case 4 are the only valid options. Let us explore what happens in these two cases once the logicians factor this in
3) night 1: The tallest and second tallest still both leave due to the explanation given for case 3 above. The third tallest also leaves because he knows the two tallest have blue dots and he sees a blue dot therefore he knows he must have a red dot.
night 2-forever: The shortest person does not know what color dot he has since (as we will see in case 4) the third tallest would have left even if the shortest had the red dot
4) night 1: The same as the above explanation for case 4 (the three tallest logicians leave)
night 2-forever: the shortest person can not distinguish between case 3 and case 4 so he can not leave
Thus not everyone can leave in case 3 or 4 either which eliminates all our cases.
If you work it out like this for the five cases for n=5
1)RBBBB
2)BRBBB
3)BBRBB
4)BBBRB
5)BBBBR
You will get that the only case where everyone will be able to leave is case 5. Since everyone will know that from day one everyone will guess that the first night and leave then.