Puzzle Page

Horse Race Puzzle

Given a horse race with 5 gates and no stopwatch find the 1^st-3^rd place winners of a pool of 25 horses assuming that each horse will race consistently. How many and what races must be run in order to determine the winners.

Answer:

A total of 7 races of 5 horses each is required. Initially putting each horse randomly into a 5x5 matrix, order each column by placing in with five races. Next order each row with the winners of a 6^th race with the fastest overall (1^st place) in the upper left hand corner. A final race will assign the 2^nd-3^rd places to the remaining 5 horses in contention as illustrated in table 1.

X_1.1	X_1.2	X_1.3	X_1.4	X_1.5
X_2.1	X_2.2	X_2.3	X_2.4	X_2.5
X_3.1	X_3.2	X_3.3	X_3.4	X_3.5
X_4.1	X_4.2	X_4.3	X_4.4	X_4.5
X_5.1	X_5.2	X_5.3	X_5.4	X_5.5

table 1: Solution to the horse race problem. Following the first 5 races each row) every horse is ordered quickest (?.1) to slowest(?.5). A 6^thrace of the individual winners of the first 5 races allows us to to assign each row a relative ranking and each individual horse as X_{secondrace.firstrace}. Note that the 10 horses X_?.4-X_?.5 were eliminated in the first five races by virtue that they cannot place 1^st-3^rd. The 6^th race likewise eliminates the remainder of the last 2 rows ( X_4.?-X_5.?), plus the horses labeled X_3.3, X_3.2, X_2.3 as they will not be able to place either. With X_1.1 as the clear winner, X_1.2,X_1.3,X_2.1,X_2.2 and X_3.1 race one last time for 2^nd and 3^rd place.

Comments and continuation:

If you want to determine a fourth place winner, then you need at most only one more race.

If X_1.2 wins and X_1.3 and X_3.1 share 4^th or 5^th places in the last race, then X_1.2, X_2.1 and X_2.2 take 2^nd, 3^rd and 4^th places respectively overall without another race.
If in the last race, X_1.2 and X_1.3 take 4^th or 5^thplaces respectively and X_3.3 takes 2nd then X_1.4, X_2.2and X_3.2 must race to determine the 4^thplace overall.
Otherwise, the final races 3^rd place winner must face off against the neighbor to the final races 2^nd place winner for 4^th place overall.

Small (Squared) Generalization:

Given n² horses, n > 2, and where n = gates, then you may resolve the 1-3^rd or 1-4^th places with

[Eqn. 1] n + (2-1) + 1 {+ 1 optional and sometimes necessary for 4^th place}

races. The n x n matrix resolves to the above 5 x 5 matrix above following the n + 1^st race.

Cubit Generalization:

Given n³ horses, n > 2, and where n = gates, then you may resolve the 1-3^rd places with

[Eqn. 2] n² + n + (3-1) + 1

races. The n x n x n matrix resolves to the table 2 below 3 x 3 x 3 matrix above following the n² + n + 1^st race. Where A is the determined 1^st place winner, while B's are potential 2^nd or 3^rd place winners, and C's are potential 3^rd place winners. Note that there are at most 3 B's and 6 C's so [Eqn. 2] is really an upper bound.

`A`	`B₁*`	`C₁*`
`B₂*`	`C₂*`	`0`
`C₃*`	`0`	`0`

`B₃*`	`C₄*`	`0`
`C₅*`	`0`	`0`
`0`	`0`	`0`

`C₆*`	`0`	`0`
`0`	`0`	`0`
`0`	`0`	`0`

table 2: Table of Intermediary winners
following the n² + n^strace. A
is the overall 1^st place winner, with B's
potential 2^nd and 3^rd place winners and C's
potential 3^rd place winner.  The 3 B's race with the

n² + n + 1^st

 race with the winner taking 2nd overall,
and the runner up with the winners adjacent C and the runner up racing for 4^th
place.

n^m Generalization:

Given n^m horses, n > 2, and where n = gates, and m > 2 then looks like the m-cube will resolve to the above table 2 with

[Eqn. 3] n^m-1+ n^m-2 + ...+ n¹+ (m-1) + 1

Likewise with Eqn.2, Eqn 3 would seem to be an upper bound. This is beginning to look a lot like my recollection of game theory, if anyone knows the correct generalization and/or an appropriate game theory theorem please do let me know!