# Solution to find top 5 from 25 horses by racing 5 at a time

There are 25 horses. First 5 races can be done with random groups of 5 horses and we will get 5 Ordered Sets of Horses and then have a sixth race of all the Toppers got from above 5 races. This will give us our Topper. Let’s say, below are the five ordered sets we received and A1, B1, C1, D1, E1 is the ordered result from 6^{th} race. We will have following matrix.

A1 | A2 | A3 | A4 | A5 |

B1 | B2 | B3 | B4 | B5 |

C1 | C2 | C3 | C4 | C5 |

D1 | D2 | D3 | D4 | D5 |

E1 | E2 | E3 | E4 | E5 |

Now, A1 is the topper, we need to find next 4 and for that we can erase the candidates like E2,E3,E4,E5, because we already know B1,C2,D1,E1 are ahead of them, similarly D3,D4,D5,C4,C5,B5 can be erased from the eligible candidates.

A1 | A2 | A3 | A4 | A5 |

B1 | B2 | B3 | B4 | B5 |

C1 | C2 | C3 | C4 | C5 |

D1 | D2 | D3 | D4 | D5 |

E1 | E2 | E3 | E4 | E5 |

Now, the candidates for second position are A2, B1. We have 2 use cases here.

If position 2 =A2 | If No.2 =B1 |

Candidates for position 3 = B1,A3 | Candidates for position 3 = A2,B2,C1 |

So, possible candidates for 7^{th} race will be A2, B1, A3, B2, and C1. This race will provide top 3 horses. First position in 7^{th} race will be 2^{nd} top horse and second will be 3^{rd} top horse. Now, we need to get 4^{th} and 5^{th} positions. For that, it needs 8^{th} race with following candidates.

Topper 1 = A1 |
|||||||||||||||

Topper2 |
A2 |
B1 | |||||||||||||

Topper3 |
B1 |
A3 |
A2 |
B2 |
C1 |
||||||||||

Topper4 | B2 | A3 | C1 | B1 | A4 | A3 | B2 | C1 | B3 | C1 | A2 | A2 | B2 | C2 | D1 |

Topper5 | A3,B3,C1 | A4,B2,C1 | A3,B2,C2,
D1 |
A4,B2,C1 | A5,B1 | A4,B2,C1 | A3,B3,C1 | A2,B3,C2,
D1 |
A2,B4,C1 | A2,B3,C2,
D1 |
A3,B3,C1 | A3,B2,C2,
D1 |
B3,A2,C2,
D1 |
A2,B2,C3,
D1 |
A2,B2,C2,
D2, E1 |

Now we need to see if in each of the above usecase, one race is sufficient, which is 8^{th} race. Also, in 8^{th} race, third position from 7^{th} race will take part and so we can remove the candidates used in 7^{th} race in each usecase, as we already know their ordering amongst themselves.

So let’s take each use case and find eligible candidates for 8^{th} race, if there are more than 5, then 9^{th} race is needed else not. Let’s traverse each path in the matrix for the possible candidates, with 7^{th} race results to get 4^{th} and 5^{th} topper. Recap: 7^{th} race was between A2, B1, A3, B2, and C1.

1. If 7^{th} race 1^{st},2^{nd} positions are: A2,B1 respectively

Eligible Candidates for 4^{th} are: B2, A3, and C1. This means 3rd position in 7^{th} race will give 4^{th} topper.

8^{th} race is needed for 5^{th} position and candidates for 8^{th} race will be: 4^{th} position in 7^{th} race, B3, A4, C2 and D1.

2. If 7^{th} race 1^{st},2^{nd} positions are: A2,A3 respectively

Eligible Candidates for 4^{th} topper are: B1 and A4. Here 3^{rd} position in 7^{th} race is B1.

8^{th} race is needed for 4^{th} and 5^{th} positions and candidates for 8^{th} race will be: B1, A4, A5 and 4th position from 7^{th} race.

3. If 7^{th} race 1^{st},2^{nd} positions are: B1,A2 respectively

Eligible Candidates for 4^{th} are: B2, A3, and C1. This means 3rd position in 7^{th} race will give 4^{th} topper.

8^{th} race is needed for 5^{th} position and candidates for 8^{th} race will be: 4^{th} position in 7^{th} race, B3, A4, C2 and D1.

4. If 7^{th} race 1^{st},2^{nd} positions are: B1,B2 respectively

Eligible Candidates for 4^{th} topper are: B3, C1, and A2. 3^{rd} position in 7^{th} race can give either C1 or A2. So candidates who will take part in 8^{th} race will be 3^{rd} position in 7^{th} race, B3.

8^{th} race is needed for 4^{th} and 5^{th} positions and candidates for 8^{th} race will be: 3rd position from 7^{th} race, 4^{th} position from 7^{th} race, B4, C2, D1

5. If 7^{th} race 1^{st},2^{nd} positions are: B1,C1 respectively

Eligible Candidates for 4^{th} topper are: A2, B2, C2, and D1. 3^{rd} position in 7^{th} race can give either A2 or B2. So candidates who will take part in 8^{th} race will be 3^{rd} position in 7^{th} race, C2 and D1.

8^{th} race is needed for 4^{th} and 5^{th} positions and candidates for 8^{th} race will be: 3rd position from 7^{th} race (either A2 or B2 or A3), 4^{th} position from 7^{th} race (either A2 or B2 or A3), B3, C2, D1, C3, D2, E1. This scenario will need a 9^{th} race.

So, Answer to this puzzle is atmost 9 races are needed to get first 5 toppers.