^{1}⁄_{(k-1)}. So the overall probability is 1/n times 0 + 1 + ^{1}⁄_{2} + ^{1}⁄_{3} + ^{1}⁄_{4} + ... + ^{1}⁄_{(n-1)}, which is approximately ^{1}⁄_{n} (log (n-1)). It is easy to show that if we follow the strategy of skipping the first h horses and then pick the first subsequent horse that is superior to all horses so far, the probability is maximised for h = n/e. Readers who spot a connection between this puzzle and finding a lifelong partner might be bemused with the article Searching for the Next Best Mate by P M Todd, Lecture Notes in Mathematical Systems, 1997.

© Copyright 2008—2017, Gurmeet Manku.

Send me email or a
Sarahah message!