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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.