CMU Puzzle Toad: Abduction


Source: CMU Puzzle Toad

Problem: Farmer Brown is standing in the middle of his perfectly circular field feeling very content. It is midnight and there is no moon and unknown to the farmer, Martian zoologists are landing randomly at points on the circumference of his field. They land at one minute intervals, starting at midnight. As soon as there are martians at points A,B,C such that triangle ABC contains the center of the field, Farmer Brown will be teleported to the waiting space-ship and transported to spend the rest of his life as an exhibit in a Martian zoo. What is the expected time until he is abducted?

Related Problem: http://pratikpoddarcse.blogspot.com/2009/10/semi-circle-covering-n-points-puzzle.html

Solution: Posted on CMU Puzzle Toad (http://www.cs.cmu.edu/puzzle/solution33.pdf). Check my name in the acknowledgments \m/ \m/

Comments

  1. could you elaborate on what was your equation for calculating the expected value. I could not understand how the solution posted at the cmu page was derived. The equation for expected value sums up the probability , why ?

    ReplyDelete
    Replies
    1. @dontevenbother
      Consider,
      Pr(X>=1) = Pr(X=1) + Pr(X=2) + Pr(X=3) + Pr(X=4) ......
      Pr(X>=2) = Pr(X=2) + Pr(X=3) + Pr(X=4) ....
      Pr(X>=3) = Pr(X=3) + Pr(X=4) + ....
      ..
      Summing over Sum (t=1 to \infty) [Pr(X>=t)] = 1*Pr(X=1) + 2*Pr(X=2) +... = E[X]

      Delete
  2. To be more specific , would you answer be different if the question is what is the probability of n point to lie in a semi circle given n-1 points were already in a semi circle as compared to the question what is the probability that n points would lie in a semi circle?

    ReplyDelete

Post a Comment