Puzzle: What's the number on my Hat?

I got this puzzle from Gurmeet Singh Manku's blog. Awesome CS guy he is. Good one! Give it a try.
Original Link
The solution proposed by Gurmeet was wrong. I have added a comment and I hope it would be corrected in some time.

Puzzle:
A goblin forewarns N gnomes as follows: “Tomorrow morning, I shall place one hat on each of you. Each hat shall be labeled with some number drawn from the range [0, N-1]. Duplicates are allowed, so two different hats might have the same label. Any gnome shall be able to see numbers on other hats but not his own! When a bell rings, all gnomes shall simultaneously announce one number each. If any gnome succeeds in announcing the number on his own hat, all gnomes shall be set free.” The gnomes have assembled in the evening to discuss their predicament. Can you help them devise a strategy?

Solution: (correct version)
Highlight the part between the * symbols for the answer.
* Let gnomes be numbered 0 thru N-1. The i-th gnome should announce (i – s) mod N, where s is the sum of numbers he sees. With this strategy, if the sum of all N numbers equals m mod N, then the m-th gnome is guaranteed to announce the number of his own hat! *

:)

Comments

  1. Vishwas B Sharma11:43 AM, March 16, 2012

    Say the gnomes are numbered from 0 to n-1 all the gnomes from 0 to n-2 can announce the sum of all the numbers they see... Say there are five :

    a b c d e numbers on cap,

    a announces : b+c+d+e
    b announces : a+c+d+e
    c announces : a+b+d+e
    d announces : a+b+c+e

    so summing all this we get

    3*(a+b+c+d) + 4*e with this e can announce number on his hat easily.

    Generalizing, for n persons the number on the last persons cap would be :

    (Sum of all the announced numbers - (n-2)*(Sum of all the numbers last person can see))/(n-1)

    ReplyDelete
    Replies
    1. Unknown11:58 AM, June 11, 2013

      I think they cannot hear what other gnome announces.. otherwise tell first one to announce the number in one of the gnomes hat and all the gnome announces same number.. so atleast one will be right on whom first gnome has seen the number..

      Delete
    2. Unknown1:59 PM, June 11, 2013

      If they can listen to what others are announcing then there is no point in the puzzle...

      Delete
    3. Pratik Poddar9:34 AM, June 23, 2014

      Right. Correct point Jeet. Thanks.

      Delete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more