Who Owns the Zebra?

Date: 08/05/97 at 22:32:19
From: Lilly Joseph
Subject: Indirect reasoning problem

Dear Dr. Math,

I have tackled this indirect reasoning problem and have come up with a 
solution that I am not sure is correct. It is a very famous problem 
partially because nothing in the clues seems to have anything to do 
with water or zebras. It is called "Who Owns the Zebra?" and is 
comprised of 15 clues, which are the following:

 1. There are five houses in a row, each of a different color and 
    inhabited by people of different nationalities, with different 
    pets, drinks, and flowers.
 2. The English person 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 (your right) of the 
    ivory house.
 7. The geranium grower owns snails.
 8. Roses are in front of the yellow house.
 9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house on the left.
11. The person who grows marigolds lives in the house next to the 
    person with the fox.
12. Roses are grown at the house next to the house where the horse is 
    kept.
13. The person who grows lilies drinks orange juice.
14. The Japanese person grows gardenias.
15. The Norwegian lives next to the blue house.

So given the 15 clues, who drinks water? And who owns the zebra?

I would really appreciate it if you could explain how you concluded 
who owns the zebra and who drinks water. This problem requires 
carefully using logic and ruling out possiblities. I think it is the 
Norwegian who both owns the zebra and drinks water, but I am really 
not sure if my method of ruling out possibilities was correct. Please 
show me the right way. 

I want to say thank you to all the doctors at Dr. Math for making 
mathematics fun and for helping children of all ages become better 
acquainted with the endless possibilities that math can lead one to. 
Thank you for everything.

Yours truly,
Lilly Joseph

Date: 08/13/97 at 16:05:48
From: Doctor Rob
Subject: Re: Indirect reasoning problem

I first saw this problem in 1962 in a magazine called _International_
_Life_. It is probably older than that.

Who Owns the Zebra?

Of course one could just enumerate the 5^5 = 3125 different possible
answers, and scratch off all of those which didn't fit the clues, but
this is the hard way. With a little logic, the correct answer can be
deduced.

The kind of logic used goes like this:

Number the houses from left to right as 1, 2, 3, 4, and 5.

By No.2, the English person lives in the red house. This implies that
the English person does not live in the green, ivory, yellow, or blue
house, and that the Spaniard, Ukrainian, Norwegian, and Japanese do
not live in the red house.  Thus this one clue gives us nine facts.

By No.3, the Spaniard owns the dog. Again, this tells us nine facts:
the Spaniard does not own the snails, fox, horse, or zebra, and the
dog owner is not English, Ukrainian, Norwegian, nor Japanese. It also
implies that the person who lives in the red house is not the dog
owner, a tenth fact.

By No.4, coffee is drunk in the green house. Again, this tells us nine
facts: coffee is not drunk in the red, ivory, yellow, or blue house,
and tea, milk, orange juice, and water are not drunk in the green
house. It also implies that the coffee drinker is not English.

By No.5, the Ukrainian drinks tea. Again, this tells us the usual nine
facts: the tea drinker is not English, Spanish, Norwegian, or
Japanese, and the Ukrainian does not drink coffee, milk, orange juice,
or water. Also the tea drinker is not the dog owner, nor does he live
in the red house.

We'll hold off on No.6 for a bit.

By No.7, the geranium grower owns snails. Thus the geranium grower 
does not own the dog, fox, horse, or zebra, and the snail owner does 
not grow roses, marigolds, lilies, or gardenias. Thus the geranium 
owner is not the Spaniard.

By No.8, the rose grower lives in the yellow house. Thus the rose
grower does not live in the red, green, ivory, or blue houses, and the
person living in the yellow house does not grow geraniums, marigolds,
lilies, or gardenias. This implies that person living in the yellow
house does not own snails. Furthermore the rose grower does not drink
coffee.

By No.9, milk is drunk in house 3.  Thus milk is not drunk in houses 
1, 2, 4, or 5, and neither coffee, tea, orange juice, or water is 
drunk in house 3.

By No. 10, the Norwegian lives in house 1. The Norwegian does not live
in houses 2, 3, 4, or 5, and the resident of house 1 is not English,
Spanish, Ukrainian, or Japanese.  This implies that house 1 is not
red, the resident of house 1 does not own the dog nor drink tea.

We'll hold off on No.11 and No.12, too.

By No.13, the lily-grower drinks orange juice. Thus the lily-grower
does not drink coffee, tea, milk, or water, and orange juice is not
drunk by the growers of geraniums, roses, marigolds, or gardenias.
Then the lily-grower cannot be Ukrainian, live in house 3, or live in
the green house. Furthermore the drinker of orange juice cannot own
snails, live in the yellow house, live in the green house, live in
house 3, or be Ukrainian.

By No.14, the Japanese grows gardenias. Thus the Japanese does not 
grow geraniums, roses, marigolds, or lilies, and the gardenia-grower 
is not English, Spanish, Ukrainian, or Norwegian. We can deduce that
the gardenia-grower does not drink tea, own the dog, live in the red
house, or live in house 1, and further that the Japanese does not live
in the yellow house, own snails, or drink orange juice.

By No.15, the blue house must be number 2. Thus the blue house is not
numbers 1, 3, 4, nor 5, and house 2 is not red, green, ivory, or
yellow. Then milk is not drunk in the blue house, and house 2 is not
owned by the English person, nor is coffee drunk there, nor are roses
or marigolds grown there.

Now we must deal with No.6, No.11, and No.12, which deal with the 
positionof houses.

One of the things implied by No.6 is that the green house is not 
number 1, and the ivory house is not number 5. This implies that 
coffee is not drunk in house 1. In fact, there are two possibilities:  
the green house could be number 4 (and ivory number 3) or number 5 
(and ivory number 4).  Let us take them in order:

Case 1:  The green house is number 4 and the ivory house is number 3.
Then the red house is number 5 (the only possibility left), and so the
yellow house is number 1. This allows us to deduce that the Norwegian
lives in the yellow house, the Englishman in house 5 (by elimination),
roses are grown in house 1, coffee is drunk in house 4, the Norwegian
grows roses, tea is drunk in the blue house (by elimination), the
Ukrainian lives in the blue house, the water-drinker grows roses (by
elimination), the Japanese drinks coffee (by elimination), the
Spaniard drinks milk (by elimination), the English person drinks
orange juice (by elimination), tea is drunk in house 2 (by elimina-
tion), orange juice is drunk in house 5, water is drunk in house 1 (by
elimination), orange juice is drunk in the red house, water is drunk
in the yellow house (by elimination), the English person grows lilies,
the Spaniard grows marigolds (by elimination), the Ukrainian grows
marigolds (by elimination), lilies are grown by the owner of house 5
(which is red), the Ukrainian owns snails (by elimination), marigolds
are grown by the dog owner (by elimination), the milk drinker owns the
dog, the Spaniard lives in house 3 (which is ivory), and so on!

Not quite all of the remaining assignments can be made in this way.

Now we have to check No.11:  The marigold grower (the Spaniard living
in house 3, which is ivory, the dog-owner, milk drinker) has to live
next to the fox owner.  The fox owner can't be in house 2, so must be
in house 4. This implies many further facts.

Now we have to check No.12: Roses are grown house 1, so the horse must
be in house 2, which is a contradiction, since snails are kept there.
(Certainly there is a shorter way to see this contradiction!)

Case 2:  The green house is number 5 and the ivory house is number 4.
Then the yellow house is number 1 (by elimination) and the red house
is number 3 (by elimination). This implies that the English person
lives in house 3, the English person drinks milk, the Norwegian lives
in the yellow house, the Norwegian lives in house 1, the Norwegian
grows roses, roses are grown at house 1, coffee is drunk in house 5,
the Japanese drinks coffee (by elimination), water is drunk in the
yellow house (by elimination), water is drunk in house 1, the
Norwegian drinks water, the Spaniard drinks orange juice (by
elimination), the Spaniard grows lilies (by elimination), the Japanese
lives in the green house, and so on.

Now we check No.11: The house with marigolds can be either 3 or 4, so
the house with the fox can be 2 or 4, or 3 or 5, respectively, but
not 1.

Now we check No.12: The roses are grown in house 1, so the horse has
to be in house 2. This implies by elimination that the zebra is in
house 1, and the dog in house 4, the fox in house 5, and the snails in
house 3.

The rest now follows.  The results are:

House   Color     Nationality   Animal    Beverage    Flower
  1     Yellow    Norwegian     Fox       Water       Roses
  2     Blue      Ukrainian     Horse     Tea         Marigolds
  3     Red       English       Snails    Milk        Geraniums
  4     Ivory     Spaniard      Dog       O.J.        Lilies
  5     Green     Japanese      Zebra     Coffee      Gardenias

So the Norwegian drinks water, and the Japanese owns the Zebra.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/