Gnomes in Trouble (Again!)

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

Hi, 

I'm from Romania, and my English is not very good, so I apologise in
advance for my language mistakes.

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
I read the author's answer, but his solution hasn't convinced me. 

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.

Thank you in advance

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
  http://mathforum.org/dr.math/problems/adam.11.13.01.html 

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 
has a ruby, with no additional information about what the other 
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
From: Andrei Brad
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 
path the gnomes had to follow has three steps:

1. Figure out A SOLUTION

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

3. Follow "mechanically" its algorithm.

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

Thanks for your help.
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
From: Andrei Brad
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/