The 37% rule
The first question we need to answer is, why is the best strategy to throw back some number of frogs, and then kiss the next one that is better than all those you've seen so far? Well, what else could you do? All you know about the frogs that you've seen is how good they are relative to each other, which you can see from the numbers on their backs. When the first frog hops out, you have absolutely no information (the number on its back tells you nothing). You could kiss it, but there's only a 1 in 100 chance that it's really the handsome prince. So you'd be better off waiting until you've seen a few more frogs ... and that's the strategy!
Let's make things a little more general. If there are frogs in the pond, you will kick back the first frogs, and then kiss the next frog that has a higher number than all those you have seen so far. We have to work out what the best choice of is. To do that, we have to work out what your chances are of kissing the right frog, depending on where he appears in the sequence:
If the handsome prince is one of the first frogs, disaster, you'll kick him back in the pond.
If he is the th frog, success, you'll kiss him.
If he is the th frog, you'll kiss him, unless the th frog had the largest number of all the previous frogs. This unfortunate arrangement of frogs, which means that you'll kiss the th frog, not the handsome prince, only occurs in of the possible ways of arranging the first frogs. (There are just as many arrangements that have the largest numbered frog in the last position, as there are arrangements that have the largest numbered frog in any other position.) You'll kiss the right frog in of the possible cases.
If he is the th frog, you'll kiss him, unless the th or th frog had the largest number of the previous frogs. This only occurs in of the possible ways of arranging the first frogs. You'll kiss the right frog in of the possible cases.
And so on, until
If he is the th frog, you'll kiss him, unless the th, th, th,…or th frog had the largest number of the previous frogs. This only occurs in of the possible ways of arranging the first frogs. You'll kiss the right frog in of the possible cases.
Now, each of these possible positions of the handsome prince occurs in of the possible arrangements of the frogs, so your probability of winning is
We can now work out what you should use for various numbers of frogs in the pond (values of ). If there are only four frogs, we can see that
For 1000 frogs (), you should choose .
Let's plot the value of that you should choose as a function of .
As gets bigger, we can see that the proportion of frogs that you should kick back before thinking about kissing asymptotes to about . But why? Can we be more precise? Can we estimate the size of the function when is large?
Have a look at the graph drawn below.
The area of the shaded blocks is . The curve drawn through the top left hand corners of the blocks is . We can see that the area under the curve is less than the area of the blocks, so
Now look at the next graph.
In this case, we can see that the area under the blocks (excluding the first block) is less than that under the curve, so
But how often does this net you the handsome prince? We found a while ago that the probability of kissing the right frog is