Thursday, August 2, 2007

Needle in a haystack Puzzle (Intuitional Puzzle)

Intuitions plays this puzzle. Lets work on finding the needle in the haystacks
It follows:
You are one of ten contestants in the game described as below:
A field contains 100 haystacks, 10 of them have a needle. On entering the field, the first contestant searches haystacks until he finds one that contains a needle. Assume that his search of each haystack is exhaustive - that is, if he can't find a needle in the haystack, there isn't one. Assume also that each needle is hidden deeply enough within its haystack that it cannot be found without seriously disturbing the haystack.

The second contestant then enters the field, and searches haystacks until he too finds a needle. He will not search any of the haystacks searched by the first contestant, because he knows that they never contained or no longer contain a needle. Each subsequent contestant repeats this process. The winner is the contestant who has searched the fewest haystacks before finding a needle.

Suppose that you could choose whether to be the first, second... tenth contestant. Would your intuition tell you:
1. choosing to search after certain number of contestants, at what position?
2. it doesn't really matter (the positions), choose any
Do tell the reasons for doing so!!
---

2 comments:

  1. Hmm... a nice puzzle. The first contestant has a probability of 10/100 or 1/10 of finding the needle.

    The second contestant has a probability ranging from 9/99 or 1/11 to 9/9 or 1/1.

    The third contestant has chances between 8/98 to 8/8 or 1.

    Similarly, for all the contestants the probability shall be a maximum of 1 except the first one (for if his luck runs out he would have to search 91 haystacks to find his needle lifting the probability of all other participants to 1)

    For now, I can only say that I will definitely NOT be the first one to enter the haystacks, counting that he is not the luckiest person on the planet. :)

    ReplyDelete
  2. I think all the contestants are equally lucky.
    Let (x1,x2,x3,..x10) be a case representing first needle at x1 haystack , 2nd at x2 ...
    So , for a given tuple , the number of diggings that ith person makes is d(i) = x(i) - x(i-1)
    x(0) = 0
    We have to find the i for whom the expected number of diggings is the least.
    I claim that expected number of all d(i) is the same.

    Proof :
    Say (x,j,...) be a case in which d(1) = x
    we create the tuple (j-x,j,...)
    This tuple has d(2) = x
    similarly for (i,i+x,...) we construct (x,i+x,..)

    Now we can say that the number of cases in which d(1) = x is equal to the number of cases in which d(2) = x
    [ since there is a bijection between the cases d(1) = x and d(2) = x ]

    So , probability of d(1) =x is the same as probability of d(2) = x [As all cases are equally likely ]
    Hence their expected values are also same.
    [ 1 <= d(1) <= 91 ]
    [ 1 <= d(2) <= 91 ]
    So , contestant 1 and 2 are equally lucky. similarly for all other contestants.

    ReplyDelete

Subscribe via email

Enter your email address:

Delivered by FeedBurner