You have 25 horses. When they race, each horse runs at a different, constant pace. A horse will always run at the same pace no matter how many times it races.
You want to figure out which are your 3 fastest horses. You are allowed to race at most 5 horses against each other at a time. You don't have a stopwatch so all you can learn from each race is which order the horses finish in.
What is the least number of races you can conduct to figure out which 3 horses are fastest?
We will have 5 races with all 25 horses:
Let the results be (x.1 being fastest and x.5 being slowest in each set)-
1: 1.1 1.2 1.3 1.4 1.5
2: 2.1 2.2 2.3 2.4 2.5
3: 3.1 3.2 3.3 3.4 3.5
4: 4.1 4.2 4.3 4.4 4.5
5: 5.1 5.2 5.3 5.4 5.5
So, First 5 races: get 5x3 fastest, plus order of arrival; discard 2 slowest of each group:
1: 1.1 1.2 1.3
2: 2.1 2.2 2.3
3: 3.1 3.2 3.3
4: 4.1 4.2 4.3
5: 5.1 5.2 5.3
6th race among fastest of each group: keep only 3 groups that win this, say w.l.g.:
1: 1.1 1.2 1.3
2: 2.1 2.2 2.3
3: 3.1 3.2 3.3
-> Will know the fastest, say 1.1, leave him out of next races, will be left:
1.2 1.3 2.1 2.2 2.3 3.1 3.2 3.3
Say that 3.1 was slower than 2.1, then it will certainly not be second, max third. 3.2 and 3.3 therefore cannot be among the fastest three, discard them. Will be left:
1.2 1.3 2.1 2.2 2.3 3.1
Same for 2.3: cannot be among the fastest three, discard, only five will be left:
1.2 1.3 2.1 2.2 3.1
Set up a 7th race among these, fastest 2 are second and third of the 25.
We will have 5 races with all 25 horses:
Let the results be (x.1 being fastest and x.5 being slowest in each set)-
1: 1.1 1.2 1.3 1.4 1.5
2: 2.1 2.2 2.3 2.4 2.5
3: 3.1 3.2 3.3 3.4 3.5
4: 4.1 4.2 4.3 4.4 4.5
5: 5.1 5.2 5.3 5.4 5.5
So, First 5 races: get 5x3 fastest, plus order of arrival; discard 2 slowest of each group:
1: 1.1 1.2 1.3
2: 2.1 2.2 2.3
3: 3.1 3.2 3.3
4: 4.1 4.2 4.3
5: 5.1 5.2 5.3
6th race among fastest of each group: keep only 3 groups that win this, say w.l.g.:
1: 1.1 1.2 1.3
2: 2.1 2.2 2.3
3: 3.1 3.2 3.3
-> Will know the fastest, say 1.1, leave him out of next races, will be left:
1.2 1.3 2.1 2.2 2.3 3.1 3.2 3.3
Say that 3.1 was slower than 2.1, then it will certainly not be second, max third. 3.2 and 3.3 therefore cannot be among the fastest three, discard them. Will be left:
1.2 1.3 2.1 2.2 2.3 3.1
Same for 2.3: cannot be among the fastest three, discard, only five will be left:
1.2 1.3 2.1 2.2 3.1
Set up a 7th race among these, fastest 2 are second and third of the 25.
Divide all the horses in group of 5
Let A, B, C, D and E are 5 groups.
now pick fastest from each group and let them have a race (6th race)
so now we have fastest.
Now let us assume that fastest has come from from group A.
now pick 2nd and 3rd from Group A(because they might be faster than 2nd and 3rd of 6th race), 2nd from the group from which 2nd of 6th race belongs (as that might be faster than 3rd of 6th race) and 2nd and 3rd from 6th race.
Now have a final race and choose 2nd and 3rd from this final race.
We will have 5 races with all 25 horses:
Reply 5Let the results be (x.1 being fastest and x.5 being slowest in each set)-
1: 1.1 1.2 1.3 1.4 1.5
2: 2.1 2.2 2.3 2.4 2.5
3: 3.1 3.2 3.3 3.4 3.5
4: 4.1 4.2 4.3 4.4 4.5
5: 5.1 5.2 5.3 5.4 5.5
So, First 5 races: get 5x3 fastest, plus order of arrival; discard 2 slowest of each group:
1: 1.1 1.2 1.3
2: 2.1 2.2 2.3
3: 3.1 3.2 3.3
4: 4.1 4.2 4.3
5: 5.1 5.2 5.3
6th race among fastest of each group: keep only 3 groups that win this, say w.l.g.:
1: 1.1 1.2 1.3
2: 2.1 2.2 2.3
3: 3.1 3.2 3.3
-> Will know the fastest, say 1.1, leave him out of next races, will be left:
1.2 1.3 2.1 2.2 2.3 3.1 3.2 3.3
Say that 3.1 was slower than 2.1, then it will certainly not be second, max third. 3.2 and 3.3 therefore cannot be among the fastest three, discard them. Will be left:
1.2 1.3 2.1 2.2 2.3 3.1
Same for 2.3: cannot be among the fastest three, discard, only five will be left:
1.2 1.3 2.1 2.2 3.1
Set up a 7th race among these, fastest 2 are second and third of the 25.
Thanks for the solution.. \../
Reply 0Divide all the horses in group of 5
Reply 2Let A, B, C, D and E are 5 groups.
now pick fastest from each group and let them have a race (6th race)
so now we have fastest.
Now let us assume that fastest has come from from group A.
now pick 2nd and 3rd from Group A(because they might be faster than 2nd and 3rd of 6th race), 2nd from the group from which 2nd of 6th race belongs (as that might be faster than 3rd of 6th race) and 2nd and 3rd from 6th race.
Now have a final race and choose 2nd and 3rd from this final race.
total races will be 7.