TADM2E 1.29

Answer: Seven races.

First 5 races: Divide 25 horses into 5 groups and that gives you 5 winners.

Sixth race: Now race 5 of them that will give you winner and which two are the bottom most group. Reject bottom two group

Now consider first 3 groups, G1, G2 and G3

G3 Group (the horse that came 3rd in 6th race) - can only bid for 3rd place so we take him for next level i.e. G31

G2 Group (the horse that came 2nd in 6th race) - can bid for 2& 3rd spots we take top two from this group for next level i.e G21, G22

G1 Group (the horse that came 1st in 6th race) - can bid for 1,2,3rd place; but we have already got our first; so we need only to take 2 from this group for next level i.e. G11, G12, G13

Seventh Race:: G12, G13, G21, G22, G31 Race them to get 2nd and 3rd winner G11 is already won as 1st winner.

--Max 07:06, 16 June 2010 (EDT)

I get the same answer but want to clarify the notation and solution approach.

Answer: Seven races.

First five races: First 5 exclusive groups of 5 horses.

Sixth race: Between all the first place winners in first five races (leaders). Letter the groups by the order the leaders in the sixth race (e.g. a1 is the fastest of the leaders while e1 is the slowest leader).

Let's list the constraints implied by these results (where >> means faster).

X(n) >> X(n+1), a1 >> b1, b1 >> c1, c1 >> d1, d1 >> e1

These constraints allow us to sketch a tree of continuations for the possible ordering:

a1
| \   
a2 b1--c1--d1--e1
|  |   |   |   |
a3 b2  c2  d2  e2

Now, we need to devise the next race to give us an answer. Reasoning by constraints and seeking three fastest we can knockout anyone lower than c1 since that would imply that c2 >> b1 >> c1 which is a contradiction.

That leaves us with one more race between a2, a3, b1, b2, c1 to determine the second and third fastest horses.

Argument: In the above solution we are assuming that the winners of each of the groups are better than all the remaining horses in every group. But that might not be true. For example, let us denote the speed (20) of a horse A as A(20). Now let us consider a collection of 9 horses:

Group I A(10) B(20) C(30) winner: C(30)

Group II D(40) E(50) F(60) winner: F(60)

Group III G(70) H(80) I(90) winner: I(90)

We clearly see that if we continue with ONLY the winner of the groups, we get an incorrect answer. We need to pick the top 3 of each group to get the correct answer.