Problem: You have 5 race horses and the only available track has just 3 lanes. How many races does it take to rank the horses from fastest to slowest?
Notes: I'll assume that racing each horse against each other horse is not only sufficient to achieve the needed ranking, but is also necessary.
There are C(5,2) = 10 such head-to-head pairings, where C(5,2) stands for the number of combinations of 5 things taken 2 at a time. (If you've taken a class on graph theory, you'll remember that a complete 5-pointed star has 10 edges.)
A lower bound is 4 races, as we can only get information on a maximum of 3 pairings (1st vs 2nd, 2nd vs 3rd, and 1st vs 3rd) from any given race, and ⌈10/3⌉ = 4.
A solution: Let's call the horses Affirmed, Big Brown, Citation, Donau, and Exterminator, or A, B, C, D, and E, for short.
Note: For you racing geeks, these horses were the Kentucky Derby winners in 1978, 2008, 1948, 1910, and 1918, respectively. Affirmed and Citation went on to win the Triple Crown.
The first race pits A against B and C, and the second race pits C against D and E. We've now accomplished 6 pairings, with 4 remaining.
The third race involves A, D and E, and the fourth involves B, D and E. Each of these races provides new information on an additional 2 pairings (A vs D, A vs E, B vs D, and B vs E). This brings the total number of pairings to 10.
In this way, we've obtained the needed information in 4 races.
Note: It appears that in the general case where there are h horses and l lanes, a lower bound on the required number of races is ⌈C(h,2)/C(l,2)⌉ = ⌈h(h−1)/l(l−1)⌉. The numerator of the left-hand side of this equation is the total number of pairings involving all of the horses, and the denominator is the number of pairings in any given race.