## race horses

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 A, B, C, D, and E. 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 expression involving combinations is the total number of pairings involving all of the horses, and the denominator is the maximum number of pairings in any given race. A crude upper bound is simply C(h,2), the total number of pairings.