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)

Posting solution since no one has solved it till now.

ReplyDeleteSolution at http://www.cs.cmu.edu/puzzle/Solution16.pdf

Let us look at the world through the eyes of the hungry lion, that is, the lion is stationary but everything else moves around. Assuming furthermore that the poor animal has a stiff neck and cannot rotate its head and is always facing North. The trajectory of the center of the arena looks in the the following way: It is a combination of linear segments pointing South and circular arcs. The total length of the linear segments is 30 km. Since the center is never more than 10 meters away from the lion, the initial and ﬁnal positions of the center are at most 20 meters apart. By a form of the triangle inequality, the total length of arcs is at least 30, 000 − 20 = 29, 980 meters. But each arc has radius at most 10 meters, so the sum of all arc angles is at least 2, 998 radians.

ReplyDeletevery old puzzle but still I would like to say that assume lion is very smart and wish to reduce the amount of angle it requires to turn, so he moves in infinitesmall segments along the circumference so that in min movement in terms of angle he gets the max distance. So 2*pi radians gives him 20*pi m, i.e. 10 metre per radian, So for 30 km angle min required wud be atleast 3,000 radians.

ReplyDelete