Classic 25 Horse Race Problem :
You have 25 horses and a race-track on which you can race among at most 5 horses.Outcome of a race only tells you the relative speeds of the horses in the race.At least how many races are required to find 3 fastest horse?
Ans : 7 races
- Divide the horses into 5 groups of 5 horses each.(Randomly)
- Make a race among each group.(Total 5 races.)
- Now you can eliminate 2 horses from each group which came 4th and 5th in their group race.(Reason : Horses which are 4th and 5th fastest in their group can't be in top 3 among all horses.)(15 horses left)
- Make a race between winners of each group.(6th race)
- The winner of the race will be the fastest horse among 25 horses.(14 horses left - fastest horse has been decided)
- Now you can eliminate horses which came 4th and 5th in race and their respective group also.(8 horses left - fastest horse has been decided)
- The horse which came third in the 6th race is the only candidate from its group.(Reason:It is the fastest in its group.It came third so others in the group will not be fastest 3 horses.)(6 horses left - fastest horse has been decided)
- The horse which came second in the 6th race and its successor in its group are only candidate,the third horse of this group will be eliminated.(5 horses left - fastest horse has been decided)
- Make a 7th race between Second and third fastest horse of a group whose fastest horse came first in 6th race,Runners up of 6th race and second fastest of its group,Second Runners up of the 6th race.
- The result of the 7th race will decide the second and third fastest horse.
