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 number of pairings in any given race. A crude upper bound is simply C(h,2), the total number of pairings.

cactuspear home
comments to comments at cactuspear dot org