Using your Head is Permitted

April 2011 solution

The answer is that the probability of the frog making n hops to win against the frog making m hops is n/(n+m), regardless of the distribution, D.

To show this, we prove a property even more general. Supposing that instead of a distribution, D, we have a multiset of positive real numbers, S, of size z=n+m. The first frog picks, arbitrarily and uniformly, an element s of S, removes it from S, then hops a distance of s. It then repeats this procedure n times for n hops. The second frog then repeats the same procedure on the remaining m elements of S. Our stronger claim is that the probability of winning will remain n/(n+m)=n/z even in this case, regardless of S.

Once we show that the claim is true in this scenario, showing that it is true for any D is simple: first, draw z numbers, S1, ..., Sz from D, then have the frogs jump these distances. The probability density of drawing any particular sequence of length z is the same as the probability density of allotting any permutation of the same sequence. The win probability over all these, together, is, per the claim, n/z, regardless of D. Taking a weighted mean over all possible values of S that can be drawn from D, we necessarily also get n/z.

The case n=m=1, for a multiset S containing two distinct numbers yields a probability of 0.5 by simple symmetry. Translating to D terminology, This handles the case of a distribution D where the probability of a tie is zero.

More interesting is the case n=2, m=1. We divide this into two cases. In the simple case, some S3 is greater or equal to S1+S2. In this case, the frog that chose S3 wins with probability 1, satisfying a total winning probability of 2/3, as desired. The remaining case is one where the elements of S can form a triangle. The n-frog wins if the angle between its two hops is larger than the angle between the two hop lengths in the triangle. Because the sum of a triangle's angles is 180 degrees, the average is 60, so the win probability is, again 2/3.

The case n=1, m=2 yields a probability of 1/3, by symmetry.

Suppose, now, we have z>3. Define P(n;z) to be the probability of a frog hopping n strides winning against a frog hopping z-n strides. We want to prove P(n;z)=n/z. The trick is to look at sequences of steps made by any frog as a single large step. For example, supposing that we take S and divide it into three sets of sizes a, b and c. Given any set of angles between the hops within each set, we can calculate xa, xb and xc, the distances associated with these hops when viewed as a single large hop. We do not know, at this point, the probability that a frog taking the strides of the set of size a will win against a frog taking the rest of the strides, but we do know that if we take three different frog matches and assign in one match the distances xa and (xb,xc), in the second match the distances xb and (xa,xc) and in the third match the distances xc and (xa,xb), the sum of the three winning probabilities for the frog making one step to win is 1.

Because this sum is a constant, the fact that we take a complicated weighted mean over its values when we consider other angles or other values for the basic step sizes does not matter, and we are sure that P(a;z)+P(b;z)+P(c;z)=1 for any a+b+c=z. This, combined with the obvious P(a;z)+P(b;z)=1 for a+b=z, is enough to prove P(n;z)=n/z.

For example, we can show

P(2;z)=1-P(z-2;z)=P(1;z)+P(1;z)=2P(1;z)
P(3;z)=1-P(z-3;z)=P(1;z)+P(2;z)=3P(1;z)
...
P(k;z)=kP(1;z)

and then combine this with

1=P(1;z)+P(z-1;z)=zP(1;z)

to obtain P(1;z)=1/z, and then P(n;z)=n/z, as required.

Back to riddle

Back to main page