Associated Topics || Dr. Math Home || Search Dr. Math

### Gnomes in Trouble (Again!)

```Date: 04/26/2002 at 11:27:04
Subject: the gnomes are in trouble again

Hi,

I'm from Romania, and my English is not very good, so I apologise in

I found your site a few days ago. I've browsed through the archives
and seen interesting problems and answers, but the one with the
gnomes I like in particular. Here's another one:

The ten gnomes are free again. Their encounter with the harsh king
had a happy ending - all ten survived - but the poor creatures are
haunted by bad luck. They are captured by an evil oriental sultan who
has three hobbies: puzzles, collecting precious stones, and impaling
his enemies and/or subjects.

He promises the gnomes to set them free if they successfully pass the
following test: They will sit in a room, each individual with a box in
front of him. The first gnome will leave the room and can return and
retake his place only after the sultan places in the first box a
single stone from a large bag full of rubies and emeralds. The same
process is repeated for each gnome until each box contains a stone
(ruby or emerald).

Now: every gnome knows what kind of stone is in all other nine boxes,
except his own. Then the sultan says: "I'll give you a command and
I'll say it no more than ten times. If, after the tenth call, you
don't obey this command then I'll...(guess what!) all of you!".

Then the sultan proceeds to say his command: "All those, and only
those, of you who have a ruby in your box bring them to me." Nobody
moves. After a while the sultan says it again, and again nobody
moves. The same scenario repeats a third, fourth, and fifth time.

But after sultan's sixth call, six gnomes stands up and bring their
boxes at sultan's feet. Needless to say, all six boxes contained only
rubies and the remaining four gnomes had only emeralds in theirs.

QUESTION: What was their strategy? How did they reason? (They are not
allowed to use secret signs or other dirty tricks).

Another observation: The author doesn't specify but implies in his
description is that the gnomes could not discuss their strategy in
advance but must rely only in their individual wit and empathy.

Four years ago I found this problem in an old book and it has bothered
me ever since.  This is an adaptation (I wanted it to be a gnome
sequel), but save for the names of leading characters, everything is
the same as the original one. I tried to solve it, but I couldn't, so

It's not that I found a flaw in it, but I don't fully understand that
type of logic (if correct). If you think is worth investing your time
in it, please send me your solution (if any). If you are still
interested, I'll send you the author's answer.

```

```
Date: 04/28/2002 at 13:22:49
From: Doctor Rick
Subject: Re: the gnomes are in trouble again

Hi, Andrei.

Thanks for the interesting puzzle! It makes a nice sequel to

Gnomes and Hats

By the way, have you seen this other colored-hat probability problem?

Probability and the Prisoner Problem
http://mathforum.org/dr.math/problems/nick.07.04.01.html

Moving on to your puzzle, I am wondering if there might be a piece
missing.

Here is my thinking, working backward. Each of the 6 gnomes who come
forward on the sixth call must be thinking something like
this: "There are five gnomes that I know have rubies in their boxes.
If I had an emerald in mine, then each of these would know of only
four gnomes with rubies. They would have concluded before the fifth
call that they had rubies. Since they did not come forward on the
fifth call, I must have a ruby in my box."

The big question is, how could those five hypothetical gnomes have
concluded that they had rubies? Presumably they would have gone
through the exact same thought process, but with one fewer call
already given, and one fewer ruby known to be in another gnome's box.

We can follow this process back five steps, to the time before any
command has been issued. Here we find a hypothetical gnome who knows
all the others got emeralds. Somehow he is able to conclude that he
gnomes have concluded. How can he do this? I can only see one way: if
all the gnomes know that AT LEAST ONE RUBY WAS PLACED IN A BOX. Then
a gnome who knew all the others got emeralds would be ready, at the
first command, to come forward: he knows he got a ruby.

Did you omit, in your retelling, something that would indicate to the
gnomes that the jewels were not all emeralds? Or does the author, in
his explanation, use this fact - suggesting that the fault is in the
presentation of the original puzzle?

If I am right, here is a forward-moving version of the solution to
the puzzle.

Suppose only one gnome got a ruby. Then he would know that all the
others got emeralds, so he would know he must have a ruby in his box.
At the first call he would go forward.

Suppose now that two gnomes got rubies. Then each of these would see
that one other gnome got a ruby. He could reason: If I had an
emerald, then the other gnome with a ruby would have known it and
come forward at the first call. Since he didn't, I must also have a
ruby." Then each would come forward at the second call.

Likewise, if three gnomes had rubies, then after no one came forward
at the second call, each of the three gnomes with rubies would know
that there can't be just two rubies, or the two would have known it
and gone forward on the second call. There must be three rubies. At
the third call all three would come forward.

Jumping ahead to the sixth call, each gnome who knows that five other
gnomes got rubies would know that there must be six rubies and he has
one of them. Therefore all six go forward, and the ten gnomes are
freed.

What do you think? Is this anything like the author's explanation?
Does it clear anything up for you?

- Doctor Rick, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 05/02/2002 at 11:09:36
Subject: the gnomes are in trouble again

What was puzzling me in the first place was how (or better, why) they
choose the SAME solution without a preliminary discussion. I was
wondering what is the chance that ten individuals will came upon the
same answer out of many (possible) answers. But after you've given me
the SAME answer as the authors, I think I understand: because there
is ONLY one solution.

The problem with the hats had many possible solutions, including some
trivial ones (choosing at random), and even if every gnome found
the maximum win solution, they had to agree on what colour to count
before the test.

In the stone problem the situation is slightly different. The logical

1. Figure out A SOLUTION

2. Realise that is THE SOLUTION, the ONLY reasonable one.

Step 2 was the missing link in my logical chain and without it
my "intuition" couldn't grasp the outcome.

Andrei
```

```
Date: 05/02/2002 at 22:31:23
From: Doctor Rick
Subject: Re: the gnomes are in trouble again

Hi, Andrei, thanks for responding on this.

I'm not sure I understand what you are saying. The basic idea is that
each gnome must know the other gnomes well enough to trust that they
will be able to figure out the problem logically just as he has. He
sees that, if he saw no rubies, he could deduce that he had a ruby;
so he assumes that any of the other gnomes would be able to do the
same. Likewise, if he saw one ruby, then (assuming that any of the
other gnomes could deduce that he had a ruby if he saw no rubies), he
could deduce after the first unanswered call that he must have a
ruby; so he assumes that any of the other gnomes could make this same
deduction. And so on until we get to the actual situation, in which
he sees 5 rubies and no gnome has answered the first 5 calls.

The big question, which I asked you and you have not answered, is:
Was there any basis for a gnome to know that he had a ruby if he saw
that none of the others had a ruby? The only way I can see for him to
do so is if he knows that at least one of them must have a ruby; but
this is not deducible from the problem as you stated it. Is there
anything in the statement of the original puzzle that you omitted,
that would provide this information?

- Doctor Rick, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 05/13/2002 at 07:06:10
Subject: the gnomes are in trouble again

You were right, I forgot the condition that at least one stone must be
different from the others!
```

```
Date: 05/13/2002 at 08:15:16
From: Doctor Rick
Subject: Re: the gnomes are in trouble again

Thanks, Andrei. I'm glad to have the mystery resolved, and to know
that my guess was correct.

- Doctor Rick, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Probability
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search