Skip to main content

Einstein's Logic Puzzle (SPOILER ALERT!)


On Monday I began working through a Discrete Math textbook in preparation for some courses I'll be taking in January. There was a beautiful logic problem in Chapter 1, apparently created by Einstein. This is one version of it:

Five men with different nationalities and with different jobs live in consecutive houses on a street. These houses are painted different colors. The men have different pets and have  different favorite drinks. 

Determine who owns a zebra and whose favorite drink is mineral water (which is one of the favorite drinks) given these clues: 
  1. The Englishman lives in the red house. 
  2. The Spaniard owns a dog. 
  3. The Japanese man is a painter. 
  4. The Italian drinks tea. 
  5. The Norwegian lives in the first house on the left. 
  6. The green house is immediately to the right of the white one.
  7. The photographer breeds snails. 
  8. The diplomat lives in the yellow house.
  9. Milk is drunk in the middle house.
  10. The owner of the green house drinks coffee.
  11. The Norwegian’s house is next to the blue one. 
  12. The violinist drinks orange juice. 
  13. The fox is in a house next to that of the physician. 
  14. The horse is in a house next to that of the diplomat.

Initially there are 600 (5! for each row) possible combinations. 
Using the clues we can immediately reduce this like so:

Number 1 2 3 4 5
Color




Nationality Norwegian



Job




Drink

Milk

Pet





This is a table representing the fields with the currently known values using CLUES 5, 9, 11. 
There are now only 312 possible combinations of the remaining fields.

SOLUTION
1. Right away, you can find the color of the Norwegian's house using CLUES 1 and 6 (on top of those you have used already.)
    • CLUE 6 tells you that the WHITE and GREEN houses are adjacent. Therefore, neither can be HOUSE 1-they must be two of the houses from HOUSE 3,4 or 5.
    • CLUE 1 tells you that the Englishman has a red house. Therefore, by process of elimination, the Norwegian's house must be yellow.
Number 1 2 3 4 5
Color




Nationality Norwegian



Job




Drink

Milk

Pet





Remaining possible combinations : 294

2. Now, using CLUES 8 and 14,  we discover that the Norwegian is the DIPLOMAT and the house next to him  contains the HORSE.
Number 1 2 3 4 5
Color




Nationality Norwegian



Job Diplomat



Drink

Milk

Pet
Horse



Remaining possible combinations : 112

 3. Look at clues 4, 10, and 12. The Norwegian can't drink milk (since he lives in HOUSE 1), he can't drink ORANGE JUICE as he isn't the violinist, he can't drink TEA (CLUE 4) and he can't drink coffee(CLUE 10). 
 Therefore he drinks  mineral water.
Number 1 2 3 4 5
Color




Nationality Norwegian



Job Diplomat



Drink Mineral Water
Milk

Pet
Horse



Remaining possible combinations : 84

4. At this point it makes sense to list the remaining possibilities. I find it easiest to organise by NATIONALITY, like so: 

Nationality Norwegian Englishman Japanese Italian Spaniard
Number 1 3, 5 2,3,4,5 2,4 3,4,5
Color Yellow Red Blue, White, Green Blue, White Green, White
Job Diplomat Violinist, Physician, Photographer Painter Violinist, Physician, Photographer Violinist, Physician
Drink Mineral Water OJ, Milk Coffee, Milk Tea Coffee, OJ, Milk
Pet Zebra, Fox Zebra, Fox, Snails Horse, Fox, Zebra Horse, Fox, Zebra,Snails Dog
We've reduced the number of remaining combinations significantly. 

4. From this point we can take a gamble and place the Englishman. There are two possibilities: because the WHITE and GREEN HOUSES are adjacent, one of them has  to be HOUSE 4. Therefore, the Englishman is either in HOUSE 3 or 5. So one of these scenarios is correct:
3 4 5 # 3 4 5



#





#





#


Milk

# Milk

5. If the Englishman is in HOUSE 3, then he must drink MILK. If so, then the Japanese man must drink COFFEE and therefore lives in the GREEN house. We continue through eliminating duplicates until we get this:

Nationality Norwegian Italian Englishman Spaniard Japanese
Number 1 2 3 4 5
Color Yellow Blue Red White Green
Job Diplomat Physician Photographer Violinist Painter
Drink Mineral Water Tea Milk OJ, Coffee
Pet Fox Horse Snails Dog Zebra
Go back and check to see if all clues match this table. If so, then we've solved it. We were lucky in choosing HOUSE 3 for the Englishman first. However, if we had tried HOUSE 5 and found a logical inconsistency, we would have known immediately that the Englishman was in HOUSE 3.


After I had solved the puzzle this way, I discovered these grids online:
 In these grids, you place a circle for fields that match (i.e. Englishman in Red House). Then you place crosses through the remaining columns and rows (So X's would go in the Red column for the remaining people.)

I'm not sure which method is faster.
Labels:

Comments

Post a Comment

Popular posts from this blog

Venturing into Number Theory

In attempt to solve a maths problem with Ruby, I discovered the benefits of going beyond simple arithmetic. Perhaps surprisingly, many seemingly complex mathematical problems can be solved using basic arithmetic and raw computing power. Most of the time this doesn't pose a problem. However, as the values involved grow larger, the demands on the computer's memory reaches a critical point beyond which you risk crashing your computer.  The problem I was trying to solve was the following:    What is the smallest positive number that is evenly divisible  by all of the numbers from 1 to 20? After causing my computer to hang for several minutes, I realized I had to rewrite the program I was working on. The program had to take shortcuts, so that instead of testing every single value between 1 and 1 million, it only tested likely values. With the help of my lovely wife (a Maths teacher) I rewrote the program using prime numbers.   class SmallestProduct requ...
Post a Comment
Read more

CodeSchool vs Codecademy(or 'How socket inherits event listening methods and implements asynchronicity')

In this review I'm going to focus on the pedagogy that I see evident in some CodeSchool courses and compare them to  Codecademy. By pedagogy, I mean: 'How does CodeSchool teach?' and ' Does it do a good job of teaching?'. I'm going to argue that despite high quality videos, colourful web pages, and often ssspppeeeeeakkkiiiing...rrrreeally...slowly..., CodeSchool's pedagogy is inferior to that of Codecademy. There are many fantastic resources for learning to code on the web, and CodeSchool is one of them. So far I have completed courses in Ruby, Rails, Javascript, HTML/CSS, Jquery and Git on CodeSchool. The courses have all included high quality videos and colourful, interactive exercises- as well as  massive  pdf files of the slides ( the files take more than a minute to load on my machine .) The question is: does the higher production value mean better educational quality? The 'Try' courses on CodeSchool(such as Try Ruby and Try jQuery) are f...
Post a Comment
Read more