Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Jan 20, 2011

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/


  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 ?

    1. @dontevenbother
      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]

  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?