» MAKE: NOISE — Discuss this article

Showing messages 1 through 9 of 9.

• Gnomes
  You must be logged in to reply.
  
  
  I read the gnomes puzzle before starting a big drive, and felt clever coming up with a solution to save 96 in the worst case. Now that I've seen the simple and correct 99 answer, it seems somewhat pointless to continue with mine. But, mine feels very different, I thought I'd pass it on.
  
  My original idea was to have some gnomes count and pass on the information to the rest. Using red/blue as binary, 7 gnomes could represent all numbers from 0-127. So, if the first 7 gnomes counted the number of red hats, and stated their answer in this code, the remaining 93 gnomes could easily answer by keeping track of that count. In the worst case, the wizard could set things up so that the first 7 gnomes fail.
  
  A refinement would be to make the 1st gnome's red/blue be a "normal" = red vs. "inverse" = blue. Now, gnomes 99-92 are the counters. Gnome 100 looks at the count, and how many of 99-92 are "right" or "wrong". 100 choosed whatever makes the most right. Now, in the worst case, that is a 4/3 split. (for example, if 5 are wrong and 2 are right, gnome 100 would call out "inverse", making 5 right and 2 wrong). Now, the worst case is:
  -Gnome 100 fails
  -3 of the 7 counters fail
  For a total of 4. Saving 96.

  Posted by oberman77 on August 19, 2007 at 05:32:08 Pacific Time

• Race solution mistake.
  You must be logged in to reply.
  
  
  In the paragraph about Jason, the writer incorrectly states that Jason has to have 14 points right after the part where it is shown that Jason must have 13 points. The paragraph that begins with "Now we know Jason had 14 points" should be rewritten as:
  
  "Now we know Jason had 13 points. If he got four 4's for consistency, it wouldn't work (already over 16). If he got four 2's, it also wouldn't work (8 points plus the maximum 4 is 12). So he had to have received four 3's. and since he couldn't have gotten a 3 from the roller skate race, that is where he received a 1."
  
  The soultion turned out right but there was a problem with the four 2's part. I think the writer intended to put four 2's plus the max 4 is only 12 points, since of course all the first places are already accounted for so the max possible for Jason is a second place and hence, 4 points.

  Posted by jsanders on September 05, 2007 at 03:15:23 Pacific Time

• Race solution mistake.
  You must be logged in to reply.
  
  
  You're right! I'll get that fixed asap

  Posted by MichaelPryor on September 05, 2007 at 08:59:37 Pacific Time

• "Better" answer
  You must be logged in to reply.
  
  
  I would like to propose a "better" solution. It doesn't actually increase the "number of gnomes that will be set free" as the problem requests so technically it's no better. However it is fairer in that it doesn't require any gnome to take worse odds than just picking randomly. If there's any chance a gnome might rebel and pick greedily rather than be entirely altruistic it's also better in that it doesn't risk having everyone lose because one gnome was unwilling to sacrifice himself.
  
  Firstly, notice that the Wizard is aware of the strategy and can always arrange for the first gnome to lose if he follows the strategy. The first gnome is fully aware of this and therefore knows full well what colour hat the wizard has put on his head -- namely whatever colour he is forced to *not* say by the strategy.
  
  My suggestion would be to have the first two gnomes collaborate to convey that first bit of information about the remaining 98 hats they can both see. If they say the same colour that signifies "even" and if they say different colours that signifies "odd". The first gnome picks randomly and the second gnome follows appropriately.
  
  This gives the first gnomes both 50/50 odds of surviving. The wizard is given the choice only of arranging either a) getting 0 or 2 gnomes randomly or b) getting precisely 1 gnome but randomly chosen from between the first two.
  
  In the original correct answer they have to trust that the first gnome is knowingly sacrificing himself to certain doom to save them all. If he rebels then he goes free and everyone else is imprisoned. In my strategy neither of the first two gnomes do any better by rebelling. That should give the remaining gnomes some comfort.
  

  Posted by gsstark@mit.edu on September 09, 2007 at 09:06:31 Pacific Time

• Technicolor Hats
  You must be logged in to reply.
  
  
  I'm a bit late to the party, but I wanted to point out that the gnome-hat solution can be generalized. If the wizard chooses 3 or four (or 100) different colors of hats, they can still save 99 gnomes.
  
  Step 1: Rank the hat colors (red=0,blue=1,green=2, . . .)
  Step 2: Gnome #100 uses the same ranking to report the sum of the values of the hats in front of him modulus the number of different hat colors.
  Step 3-101: Each successive gnome reports his own hat color by performing the same sum-mod-colors operation and comparing it the the previously reported sum.
  
  I haven't worked through a good, generalized strategy if you can't rely 100% on the altruism of gnome #100. That is an interesting problem. Note as the number of hat colors increases the incentive of the last gnome to defect decreases. Would you doom 99 other gnomes to slavery if there is a 50-50 (3 colors) chance that you will still be enslaved with them? What if you were 2/3 likely to join them?
  

  Posted by erice on November 08, 2007 at 12:51:22 Pacific Time

• Gnome Solution - What am I missig?
  You must be logged in to reply.
  
  
  I don't think the stradegy as stated in the posted solution is correct. The solution states, "if the number of red hats that the back gnome can see is even, that gnome will say "red". If they add up to an odd number, they will say "blue"."
  The description of the sample situation ends before stating showing this. "96 sees 46, so he knows he has a "blue" hat. etc..." Well 46 is even so he would have to say "red" and die. Then gnome 95 having a red had would see the remaining 45 red hats and say "blue" and die.
  
  Also the solution also states, "Number 98 knows that 99 said the correct hat," But 98 cannot know if 99 stated the correct hat because the published article states "All gnomes will be able to hear the answers of the gnomes behind them, but they will not know if they were led off to forced labor or if they answered correctly and were set free."
  
  Am I missing something or have I misread something? Simply saying "red" if the number of hats in front of you is even would not do any better than saying the color of the hat in front of you. Such as:
  If 50 gnomes have red and 50 have blue, and the color alternates starting at red (100=r, 99=b, 98=r, 97=b... 2=r, 1=b). Then the first gnome (100) would see 49 red hats and say "blue" and die. Gnome 99 sees 49 redhats and says "blue" and lives. Gnome 98 sees 48 red hats and says "red" and lives. Gnome 97 also sees 48 red hats, says "red" and dies.
  
  The sample eludes to a stradegy that can save 99 gnomes, but simply saying "red" if even and "blue" if odd is not what is described.
  
  If I am wrong, someone please help me understand.
  

  Posted by dtzens on November 17, 2007 at 14:25:51 Pacific Time

• Gnome Solution - What am I missig?
  You must be logged in to reply.
  
  
  First off - you're missing an N in the title.
  
  Secondly - the red=even/blue=odd rule only applies to the 100th gnome. The other 99 just count the red hats in front, and if their even/odd count is the same as the previous one they say blue - otherwise red.
  
  

  Posted by einarjon on November 21, 2007 at 13:00:51 Pacific Time

• Anyone still listening?
  You must be logged in to reply.
  
  
  I have a solution that saves 100% of the gnomes even if they can only see one hat ahead. The key is based on two factors: they are very smart and the wizard hears their plan.
  
  They plant allowed save at least half of themselves. To do this the first nome will say the hat of the gnome ahead. The second gnome ill then know his color and say it. The third gnome will say the color ahead. This way at least all of the even numbered gnomes would be saved.
  
  Because they are very smart, they know that the wizard will arrange them to foil as many as possible.
  
  So when they start, the first gnome will reverse and say he opposite color of the ha in front. Te second will then know his color and thy are both saved. The odd numbered gnomes will continue to say the opposite color of hat in front. This way all 100 know the correct color.

  Posted by jimmcko on August 17, 2008 at 08:02:48 Pacific Time

• Anyone still listening?
  You must be logged in to reply.
  
  
  But this only works if the Wizard does NOT hear the second half of the plan (the reversing scheme). I thought that the premise was that the Wizard listens into all the gnomes' planning.
  
  Or are you saying that the gnomes all come to the same independent conclusion that they should declare the reverse colors, without conferring with each other? (sounds tenuous)

  Posted by Mr. Carl on February 27, 2009 at 06:44:35 Pacific Time