Using your Head is Permitted

April 2011 riddle

UPDATE (1 May): So far, there have been no complete solutions for the April riddle. The riddle will therefore run one extra month, but with the following hint:

What if the choice of D makes no difference to the final result?

A new May riddle will be posted, as usual, in parallel to this one.

This month's riddle is a variation (I hope, a simplification) over a riddle I heard from Noga Alon, who, in turn, heard it from Peter Winkler (who is, for those who don't know this already, a highly recommended source of many good riddles). When Noga asks it, the question is one line long, but I like it better this way:

The African Cyclone frog has several species, each characterized by a distribution, D, of the distance the frogs jump in every hop. D maps into the positive reals. Each hop is identically distributed and independent of all other hops.

As part of the frogs' mating rituals, frogs of the same species occasionally compete against each other. Each starts from some point and takes a certain number of hops. The winner is the frog that gets farthest away from its starting position.

Things get more complicated, however, because African Cyclone frogs have no sense of direction. At each hop, the frogs jump in an arbitrary direction in R2. The directional distribution is uniform, and is independent of all other hops' directions and all hops' distances.

The question: given the hop-distance distribution, D, and the number of hops taken by the two competing frogs, n and m, determine the probability that the frog hopping n strides wins.

You may safely ignore ties, which can only occur in positive probability if n=m=1, and even then only for certain distributions, D. Your answer need only be correct if n+m>2.

All answers should be accompanied by a proof, of course.

List of solvers:

Hu Han (3 May 19:20)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page