Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Horses on Auction

Puzzle

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?

Source

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.

Solution

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 1(k-1). So the overall probability is 1/n times 0 + 1 + 12 + 13 + 14 + ... + 1(n-1), which is approximately 1n (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.

Previous Puzzle: Balanced Coloring

Given k arbitrary points in a grid of size m by n, is it always possible to color them either red or black such that each row and each column is balanced? A row or column is said to be balanced if the difference in the number of red and black points in it is at most one.

Next Puzzle: Polya's Urn Process

There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the urn with fewer balls?

16 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.