home>puzzle index

Horse Race Puzzle

Given a horse race with 5 gates and no stopwatch find the 1st-3rd 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 6th race with the fastest overall (1st place) in the upper left hand corner.  A final race will assign the 2nd-3rd places to the remaining  5 horses in contention as illustrated in table 1.

X1.1 X1.2 X1.3 X1.4 X1.5
X2.1 X2.2 X2.3 X2.4 X2.5
X3.1 X3.2 X3.3 X3.4 X3.5
X4.1 X4.2 X4.3 X4.4 X4.5
X5.1 X5.2 X5.3 X5.4 X5.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 6th race of  the individual winners of the first 5 races allows us to to assign each row a relative ranking and each individual horse as Xsecondrace.firstrace.  Note that the 10 horses X?.4-X?.5 were eliminated in the first five races by virtue that they cannot place 1st-3rd.  The 6th race likewise eliminates the remainder of the last 2 rows ( X4.?-X5.?), plus the horses labeled X3.3, X3.2, X2.3 as they will not be able to place either.  With X1.1 as the clear winner, X1.2,X1.3,X2.1,X2.2 and X3.1 race one last time for 2nd and 3rd place.


Comments and continuation:

If you want to determine a fourth place winner, then you need at most only one more race.  
Small (Squared) Generalization:
Given n2 horses, n > 2, and where n = gates, then you may resolve the 1-3rd or 1-4th places with
[Eqn. 1] n + (2-1) + 1 {+ 1 optional and sometimes necessary for 4th place}
races.  The n x n matrix resolves to the above 5 x 5 matrix above following the n + 1st race.

Cubit Generalization:
Given n3 horses, n > 2, and where n = gates, then you may resolve the 1-3rd places with
 [Eqn. 2] n2 + 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 n2 + n + 1st race.  Where A is the determined 1st place winner, while B's are potential 2nd or 3rd place winners, and  C's are potential 3rd place winners.  Note that there are at most 3 B's and 6 C's so [Eqn. 2] is really an upper bound.


A B1* C1*
B2* C2* 0
C3* 0 0



B3* C4* 0
C5*
0 0
0 0  0 



C6* 0 0
0 0 0
0  0 
 0 
table 2: Table of Intermediary winners following the n2 + nst race. A is the overall 1st place winner, with B's potential 2nd and 3rd place winners and C's potential 3rd place winner.  The 3 B's race with the n2 + n + 1st race with the winner taking 2nd overall, and the runner up with the winners adjacent C and the runner up racing for 4th place.



nm Generalization:
Given nm 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]  nm-1+ nm-2 + ...+ n1+ (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!

home>puzzle index