Every Tuesday, Gene publishes weekly updates to his chats.
On one Tuesday each month, Gene is online to take your questions and abuse. He will chat about anything. Although this chat is sometimes updated between live shows, it is not and never will be a "blog," even though many persons keep making that mistake. One reason for the confusion is the Underpants Paradox: Blogs, like underpants, contain "threads," whereas this chat contains no "threads" but, like underpants, does sometimes get funky and inexcusable.
Greetings, update readers.
As promised, today I will deliver two logic puzzles, with their answers. The first is the 12 Billiard Ball Problem, which I did at age 12, via staying home from school feigning illness. As I recall, it took me 16 hours. I will also give you a study guide to how to solve it, assuming you are stumped but don’t want to jump right to the solution, like the big ol wuss you are.
Then I will give you the Blue-Eyed Islander problem, which is the most diabolical I’ve ever seen. I claim no authorship there; it has been adopted by xkcd, the excellent online comic strip by Randall Munro. He didn’t invent it any more than I invented the 12 Billiard Board problem, but he has also made it his life’s work to explain it as best he can. I shall explain it better.
Know that in both of these problems, there is no cheap trick or gimmick. They are pure logic problems.
The 12 Billiard Ball Problem
You are given 12 billiard balls. One of them is very slightly lighter or very slightly heavier than the other 11; the difference is not perceptible without the use of a balance scale. You have a balance scale. In three weighings or fewer, design a system that will always find the odd ball, as well as determine whether it is lighter or heavier than the other 11. (A weighing is a weighing: If you put, say, three balls on either side, then remove one from each side to see what happens, that’s two weighings.)
What I remember about this as a kid is that there were three separate AHA! moments – genuine insights that you need to solve this correctly. Spend as much time as you like on this, and/or use these three insights as guides.
WARNING: Skip over the three insights below if you want to solve the puzzle on your own!
Insight one... is the simplest. It is simply that starting by weighing six against six is stupid: You will always get the same result, delivering almost no information: One side will always be heavier than the other, and you won’t have any idea of whether the odd ball is lighter or heavier. You get NOTHING. Have to come up with a different first weighing.
Insight two... is that when you have eliminated a ball, it is not useless. As a proven normal ball, it can be used to determine whether another ball against which it is weighed is lighter or heavier.
Insight three... is the most complex, and most valuable. It is that when you have a failure of balance between two sets of balls, you learn something important: If the odd ball is on the lighter side of the scale, it is lighter. If it is on the heavier side, it is heavier. This becomes critical.
The Solution to the 12 Billiard Ball Problem
Weigh four balls against four balls. If the balls balance, you know the odd ball is one of the remaining four. So you weigh three of those balls against three “normal” balls that were eliminated by the first weighing. If they balance, you know the remaining ball is the odd ball, and with your third weighing, you weigh it against a normal ball to see if it is lighter or heavier. You know whether the odd ball is lighter or heavier, based on how the three performed against the normal three. Say it is heavier: You then you balance one of the three against the other. If they balance, the odd ball is the third, and it is heavier. If they do not balance, the odd ball is whichever is heavier.
Okay, now what if the original four against four did not balance? Then you have also been given valuable information. You know that either one of the four balls on the heavy side is heavier than the rest, or one of the four balls on the lighter side is lighter than the rest. Aha! Let us label these eight balls as follows H,H,H,H and L, L, L, L. The first four are the suspected heavies, the second four are the suspected lights.
Here’s where it gets diabolical.
Your next measurement is three against three, specifically LLH against LLH.
If they balance, you know the odd ball is one of the two remaining ones, and that it is Heavy. With your third weighing, you weigh one against the other, and the heavier one is the odd ball.
Now, if the LLH and LLH do not balance, you have still learned important information. You know that the odd ball is one of three: Either one of the two Ls on the light side of the scale, or the H on the other. For your third weighing, weight the one L against the other. If they balance, it’s the third ball, and it’s heavy. If they do not, it’s the lighter of the two.
There is at least one other solution to this: Very similar to this, with a slight variation.
The Blue-Eyed Islander Puzzle
There is an island containing people who are blue eyed and people who are brown eyed. This island contains no reflective surfaces, including for some reason, the water. (Cut us some slack here.) No one can see the color of his or her own eyes, but can see the color of everyone else’s eyes. One day – call it day one – a visitor arrives, looks out upon the entire group of islanders, and says (truthfully) “I see at least one blue-eyed person.” Then this visitor leaves.
Now, there are a few things you need to know about the people of this island. First, is that there are exactly 200 people on the island. Second, they are all perfect, brilliant logicians. Third, they have a custom: Anytime anyone learns for certain his own eye color, he or she must leave the island that night at midnight, by ferry, never to return. Everyone in the island knows those three things, and also that their own eye color is either blue or brown.
There is one additional piece of information you, the reader knows, that is unknown to the islanders, who cannot see their own eye colors. What you now is that there are exactly 100 blue-eyed islanders, and exactly 100 brown-eyed islanders.
So, the visitor comes at noon one day, looks out at everybody’s eyes – all the islanders are present – and says “I can see at least one blue-eyed person,” then leaves. The question is: Will anyone leave the island, and when will they leave?
The answer is not that no one leaves.
HERE IS THE ANSWER.
The answer is that the 100 blue-eyed people will will leave the island on the 100th day, and everyone else will leave on the 101st.
The easiest way to explain this is to begin simply. Let’s say there was only one blue-eyed islander. He would look out at everyone else, realize no one else had blue eyes, and leave on the very first day. He’d know the visitor was talking about him.
Now, let’s say there were only two blue-eyed islanders. Each would look out at everyone else, see only one other set of blue eyes, and reason, “Well, if that person leaves tonight at midnight, I will know I have brown eyes.” When the other person doesn’t leave at midnight, then they both will realize it just after midnight, and leave the following midnight – Day 2.
Here’s where it gets harder to comprehend. Let’s say there are three blue-eyed people. Each one will see two other blue eyes, and each will go through the following computation: “Okay, let’s say I have brown eyes. Then each of these guys will go through the same computation as before, and on day two they will leave. When they don’t, then I’ll know I must have blue eyes, too, and I will leave on day three. So will they, of course”
So, a mathematical progression has been established. All blue-eyed people will leave on the day equal to all the number of blue-eyed people on the island. This makes sense mathematically, but does it make COMON sense? Won’t people, even perfect logicians, look around and say, well there are SO many blue-eyeds you just can’t conclude anything?
Well, no. We can pull it out two more step and see why. Imagine there are five blue-eyed people. Person 5 will see four blue-eyed people, numbered 1, 2, 3 and 4. Person 5 will think, okay, let’s say I have brown eyes. Person 4 will be looking at 3 and 2 and 1, and will be thinking, “okay, let’s say I have brown eyes. Then Person 3 will see only two people with blue eyes and leave on Day three. When he doesn’t, all four of us will leave on day four.” Thinking about this, Person 5 will say, okay, when person 4 doesn’t leave on day four, all of us will leave on day five…
It actually works. Now all of this will be thought about immediately after the visitor makes her announcement, and everyone with blue eyes – all the perfect logicians – will see exactly 99 blue eyes, calculate all this, and decide that on the 100th day, if 99 people have not left on the 99th day, they must all leave on the 100th.
Well, too bad. I do.
Of course, after all the blue eyed people leave on the 100th, all the brown eyed will know they are brown eyed and leave on the 101st. Most of the iterations of this puzzle do not stipulate either brown or blue (some people might be hazel, or green) in which case, nobody leaves on the 101st day.