Blog # 29 : A simple puzzle : How many races required?

You have 25 horses and 5 tracks and you need to find out top 3 horses. What is the minimum number of races required to do this ?







p.s. - Answer will be posted after 2 days from respective questions. Although we're always open for discussion in comments :)






Solution:


For 1st question:
Group 25 horses in 5 groups:

A : A1, A2, A3, A4, A5 [Decreasing order of speeds]

B : B1, B2, B3, B4, B5

C : C1, C2, C3, C4, C5

D : D1, D2, D3, D4, D5

E : E1, E2, E3, E4, E5

Five races will have to take place for ranking in groups themselves.

One race for A1, B1, C1, D1, E1 for ranking of the groups.

Now A1>B1>C1>D1>E1

So A1 is the topper. We now need to find 2 more horses for 2nd and 3rd position.

Here is the key observation.

Selection by Elimination  [We need to find 2 more horses, if any horse is slower than 2 horses except A1 then it can not be included in the solution]

1. D1 and E1 can not be included in the solution as both of them are slower than B1 and C1

and hence their whole group is eliminated as they were best from their groups.

2. A4, A5 can not be included in the solution as they are slower than A2 and A3.
3. B3, B4, B5 can not be included in the solution as they are slower than B1 and B2.

4. C2, C3, C4, C5 can not be included in the solution as they are slower than C1 which is slower than B1 itself.

So we are now having only 5 possible horses for 2 positions which can be found out in just one race. [A2, A3, B1, B2, C1] Top 2 of this group will be ranked 2nd and 3rd after A1.