You are the chief guest at an auction, where an unknown number of horses will be revealed and auctioned, one after the other, randomly permuted. You are a connoiseur of horses, and can judge whether one horse is 'better' than another. Being the chief guest, you have a one-time privilege of selecting a horse, after it is revealed, but before it gets auctioned off. You get to keep this horse for yourself. Your objective is to maximize the probability of selecting the best horse. One strategy is to pick the first horse. Can you do any better?

Posed by Huzur Saran in a mid-term in Discrete Structures course at IIT Delhi in 1992--1993. I remember that Navin Mittal and Ankur Jain were the only two persons who got this one. Problem #47(Choosing the Largest Dowry) in Fifty Challenging Problems in Probability with Solutions (1987, 88 pages) by F Mosteller is identical. The problem is also discussed in Mathematical Plums (1979, 179 pages) by Ross Honsberger.

If we always select the first horse, the probability of success is 1/n where n is the number of horses. One strategy is to skip the first horse, then pick the first subsequent horse which is superior to the first horse. The probability that the first horse is the k-th best horse is 1/n. From among the remaining k-1 horses that are superior to this horse, the probability that the best comes before all others is ¹⁄_(k-1). So the overall probability is 1/n times 0 + 1 + ¹⁄₂ + ¹⁄₃ + ¹⁄₄ + ... + ¹⁄_(n-1), which is approximately ¹⁄_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.