The Zebra Puzzle

The Setup:

1. There are five houses.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Old Gold smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house.
11. The man who smokes Chesterfields lives in the house next to the man with the fox.
12. Kools are smoked in a house next to the house where the horse is kept.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.

The Problem: Who drinks water? Who owns the zebra?

• Each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarettes.
• In statement 6, right refers to the reader's right.
• It is possible not only to deduce the answers to the questions but to figure out who lives where, in what color house, keeping what pet, drinking what drink, and smoking what brand of cigarettes.

The Solution:

house	1	2	3	4	5
color	yellow	blue	red	ivory	green
nationality	Norwegian	Ukrainian	Englishman	Spaniard	Japanese
drink	water	tea	milk	orange juice	coffee
smoke	Kools	Chesterfield	Old Gold	Lucky Strike	Parliament
pet	fox	horse	snails	dog	zebra

Coin Balancing Problems

Nine Coins - difficulty: medium
The Setup: You have nine coins that are identical in weight save for one, which is lighter than the others—a counterfeit. The difference is only perceptible by using a balance, but only the coins themselves can be weighed, and it can only be used twice in total.

The Problem: Is it possible to isolate the counterfeit coin with only two weighings?

The Solution: Divide the nine coins into three groups of three. Weigh one group against another. If the first two groups balance then the counterfeit coin is not there. Then you can take the third group and put one coin on each side. If it balances, you hold the counterfeit coin. If it doesn't balance, then the lighter coin is the counterfeit one. If the original groups of three do not balance, then put two coins from the lighter group on the balance and whichever side is lighter holds the counterfeit (or the third coin is the counterfeit if the two balance, by process of elimination.)

Twelve Coins - difficulty: hard
The Setup: You have twelve coins and a balance scale. One of the coins does not weigh the same as the other eleven, but you don't know if the odd coin is heavier or lighter than the others. The difference is only perceptible by using a balance, but only the coins themselves can be weighed, and it can only be used three times in total.

The Problem: How can you determine, in three weighings, which coin is the counterfeit?

The Solution: First weigh four coins against four coins. If they balance, you know the counterfeit is among the remaining four and can deduce it in two weighings by comparing three of the suspect coins with three you know to be legitimate (from the first weighing); this will tell you whether the counterfeit is heavier or lighter and then you can repeat the final step from the nine coin problem to isolate it.

Alternatively, if the first weighing produces uneven sides the solution is a little trickier. We now have eight suspects instead of merely four and will have to investigate more carefully. We essentially have two different tactics at our disposal:

Tactic One - Weigh the Lighter Group against a Control Group
The trick is to use the information we already know: that one group is lighter than the other group. If we swap the heavy group out for the coins we know to be legitimate (the unweighted group from the first weighing) and "the lighter group" is still lighter, we know it holds the counterfeit and that the counterfeit is lighter. Alternatively if "the lighter group" and the legitimate coins balance, the heavy group must have held the counterfeit (which would have to be heavier). But this method will only narrow the candidates down to four coins...still one too many to solve the problem with the single weighing we have left, so this tactic alone is insufficient.

Tactic Two- Swap coins from Group X and Group Y
If we swapped one coin from the heavier group and one from the lighter with each other, either the scales will tip the other way or stay the same (they can't balance because the counterfeit is still in play). If the scales change, we know one of the two we swapped is the counterfeit. If the scales are the same, we know the two we swapped are legitimate (but we would have six suspects left, and only one weighing).

If we want to get maximum information out of the second weighing and solve this puzzle, we need to combine both tactics in our second weighing. Before our second weighing, we should swap one of the lighter side's coins with one of the heavier, then replace the three remaining heavy coins with legitimate ones. This can only produce three results:

• The lighter group is now heavier - this could only happen if the counterfeit was one of the coins we swapped. Weigh one of them against a known legitimate, if the scales balance then the other one is the counterfeit. If they don't, you've found the counterfeit.
  
• The lighter group is still lighter - this could only happen if the counterfeit is lighter than a legitimate coin and was amongst the three coins originally on the lighter side. You now have three suspect coins and know the counterfeit is lighter. Repeat the final step from the nine coins problem.
• The sides balance - this could only happen if the counterfeit is heavier than a legitimate coin and was amongst the three coins removed from the heavier side. You now have three suspect coins and know the counterfeit is heavier. Repeat the final step from the nine coins problem.

Three Headed Dragon

This is a follow up to Two Headed Dragon: a Quick Logic Riddle

Three Headed Dragon - difficulty: medium
The Setup:
You walk down a long tunnel and come to the end with a door on either side. One door leads to paradise, and the other door leads to suffering, but they are both identical. A three headed dragon sits in between the doors. Each head must either lie or tell the truth. You are allowed one question to ask to help determine the correct road to paradise.

• All three heads may lie, all three may tell the truth, two heads may lie and one may tell the truth or two heads may lie and one may tell the truth.

The Problem:
What question do you ask to discover the correct door?

The Solution:

Ask, "what would your answer be if I asked you whether the first door will lead me to paradise?" and follow the dragon's advice.

This answer is also an alternate solution to the two dragon riddle.

Random Three Headed Dragon - difficulty: hard
The Setup:
You walk down a long tunnel and come to the end with a door on either side. One door leads to paradise, and the other door leads to suffering, but they are both identical. A three headed dragon sits in between the doors. One of the heads always lies, the other always tells the truth, the third answers randomly. There is no way to tell which one is which but you are allowed two question to ask to help determine the correct road to paradise.

• What the second question is, and to which head it is put, may depend on the answer to the first question.
• The random head may answer truthfully, dishonestly or totally randomly. If you asked him if he was a dragon, he may respond 'yes', 'no' or 'pizza.'
  

The Solution:

Ask dragon B, "If I asked you 'Does head A answer randomly?', would you say 'no'?" If he says no, your next question goes to head C. If he says yes, your next question goes to head A. Either way you ask, "what would your answer be if I asked you whether that door will lead me to paradise" and go through that door.

The Explanation:
The first move is to find a head that you can be certain is not Random, and hence is either True or False. If you ask dragon B, "If I asked you 'Is A Random?', would you say 'no'?" you get six possible results:

A B C Answer t=truth dragon, f=false dragon, r=random dragon
F T R yes
T F R yes
T R F yes, no or pizza
F R T yes, no or pizza
R T F no
R F T no

yes - A isn't random
no - C isn't random

Having isolated a non-random dragon, the question, "what would your answer be if I asked you whether that door will lead me to paradise?" will always produce the true answer.

Two Headed Dragon: a Quick Logic Riddle

The Setup:

You walk down a long tunnel and come to the end with a door on either side. One door leads to paradise, and the other door leads to suffering, but they are both identical.  A two headed dragon sits in between the doors. One of the heads always lies, the other always tells the truth. There is no way to tell which one is which but you are allowed one question to ask one of the heads to help determine the correct road to paradise.

The Problem:

What question do you ask to discover the correct door?

The Solution:

Ask, "what door would the other head say leads to paradise?"  then go through the opposite door.

The Analysis:

The two dragon riddle poses an excellent example of extraneous v. necessary information. At first blush, you think to solve the riddle you must deduce which dragon lies and which tells the truth. Of course, even after the riddle is solved we still never know which is which. Because we never identify the honest dragon, we instead rely on the dragons to cross check eachother's answers--one will lie about the truth, the other will faithfully report a lie. The answer we get is always wrong but we know how its wrong and can deduce the correct answer from it. If we had more questions, we could figure out both which dragon lies and which door lead to paradise--but when our question economy is limited we can only choose one.

This type of intellectual shortcut is used all the time when the opportunity costs of inquiry outweigh the utility. For instance, most people have no idea how their car's engines operates or heart pumps. In complex software coding, different programmers code different functions and may have no idea how the final software works. Like the Two Dragons riddle suggests, some information may be sacrificed in a search for answers.

Game - Blue Eyes

This was brought to my attention by G, and can be found at XKCD's site. My intention is to attempt at giving a clearer setup and clearer explanation of how to derive the answer. 

This game can be solved using a bit logic, math, and a thought experiment. I'm sure there are a variety of ways to reach the solution, but I feel that I've stumbled across a relatively easy solution, though it may be less elegant than the others. 

The Setup:

200 people--who are perfectly logical beings and completely aware of everyone else at all times--are trapped on an island. These people can see everyone else's eyes but NEVER their own (no reflection, etc.) and they have no means of communication whatsoever (no getting other people to tell you the color of your own eyes). Because they can never know the color of their own eyes, no one person knows the complete distribution of eye colors. They can only deduce the color of their own eyes from only what is given in the rest of this setup.

Every night at midnight, a ferry comes to pick up those who know, with absolute certainty, the color of their own eyes, and bring them back to the mainland. 

One morning, a guru (who happens to have green eyes) descends on this colony of logical and aware beings and makes the statement (a true one): "I see a person with blue eyes." She then disappears to never return again.

The Problem:

If there are 100 people with brown eyes and 100 people with blue eyes, how many days does it take before people can start leaving? Who can leave and how many? The answer must include 1) the color of the eyes of the people leaving, 2) number of people leaving, and 3) the number of days it takes them to leave.

Before you go off trying to solve this, there are a few things to remember.

• There IS an answer to this puzzle that fits the criteria above and does not transcend the scope of the given setup. Id est, someone leaves on a certain day. 
  
• No person initially knows the precise distribution of eye colors; that is, a person might see 100 brown eyed people and 99 blue eyed people, but does not know if he himself has brown eyes, blue eyes, or purple eyes (could be 101 brown eyes and 99 blue, or 100 brown and 99 blue and 1 purple, etc.) 
  
• Remember that in order to leave, a person must know with absolute certainty! 
  
• These people are capable of perfect logic, and know all and only what is given in the setup above.

More than arriving at the correct answer, it's more important (I think) on how you arrived at the answer. Please leave your thoughts (candidates, algorithms, and especially QUESTIONS REGARDING THE SETUP) in the comments section. I'll return periodically to leave hints and, eventually, the answer.

A Solution:
Luke used the bottom-up approach to this problem. By beginning at the simplest possible scenario, you'll find an emerging pattern. I'll begin by entertaining the thought process that a blue eyed would need to go through to achieve absolute certainty (after all, that's all that matters--you'll see later).

br = brown, bl = blue

199br, 1bl on island
The blue eyed person will realized that of the 200 people on the island, he is the only one who could have blue eyes. He leaves.

198br, 2bl on island
We'll assign letters to the two blue eyed people: A and B. A will see that B has blue eyes, and deduce that B will do the following: if B does not sees another blue eyed person, B will leave on day 1, but if B sees another blue eyed person--which must be A--B will wait to see if A leaves on day 1. Since A and B both see each other, they will both wait until day 2, realize that there must have been another blue eyed person, deduce that it is themselves, and leave that night.

197br, 3bl on island
A, B, and C have blue eyes. A will see that there are two blue eyed people and they will, at the very least, adopt the strategy above. Furthermore, if A happens to find that B and C do NOT leave on day 2, A can deduce that he has blue eyes.

There's really no point in going any further as you should see the pattern by now; many elements of which I find to be quite interesting. By the way, the answer is that all 100 blue eyed people leave on day 100.

If the number of days that blue eyed people remain on the island is greater than the number blue eyed people you see, you are the blue eyed person.