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. dontevenbother3:42 AM, June 22, 2012

    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. Unknown10:52 PM, November 07, 2016

      @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. dontevenbother4:07 AM, June 22, 2012

    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

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