Imagine that you have 25 racehorses and you want to find the fastest three.

You can stage races of up to five of them at a time, but you do not have any method of timing them (i.e. you can only see how they fare in individual races).

What is the minimum number of races needed to find the top three (not necessarily in order)?

The answer is 7.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

Still need a proof that 6 races are not enough.

Ivan Koswara
- 7 years, 1 month ago

Why didn't we have to consider the case where 1 2 3 4 5 might be the fastest among all ? For example group 12345 may already consist of the 3 fastest , or group 21 22 23 24 25 itself already consist the top 3 ? There's so many possibilities .

Lim Ken
- 7 years, 1 month ago

Log in to reply

The problem asks the minimum number of races it takes to know the fastest 3 with ANY kind of cases. Therefore we consider the worst case scenario where in all the three might be in separate groups.

Jan Edmark Arieta
- 7 years, 1 month ago

6 races are enough .From 5 races ,pick the 1st one from each race. Then winners from each race compete for position 1 2 and 3 . 7 race is not necessary .

ab k
- 7 years, 1 month ago

Log in to reply

nope, number 2 might still be faster than number 6

Zheng Wei
- 7 years, 1 month ago

Log in to reply

Please elaborate the fault in the logic .

ab k
- 7 years, 1 month ago

Log in to reply

@Ab K – Suppose the first race has horses $1,2,3,4,5$ which finishes in that order, and the second race has horses $6,7,8,9,10$ which finishes in that order. Then horses $1,6$ , and three other horses compete in the final race; suppose $1$ finishes first and $6$ finishes second. Now which of horses $2$ and $6$ is the second fastest?

Ivan Koswara
- 7 years, 1 month ago

Exactly! I did the same, got my answer wrong.

Parth Thakkar
- 7 years, 1 month ago

yeah i already did but wrong

Mohammed Nahas N
- 7 years, 1 month ago

All answers posted here are wrong...including mine

Santosh Behera
- 6 years, 12 months ago

for those who said 6, i know what you're thinking, i tried it before. I only just realised that they are asking for the TOP THREE, meaning not just the first, which is 6. you're basically listing 1-5, 6-10, 11-15 etc. and racing the winners of each of them. HOWEVER, let's say all the first numbers of each group won. then we race 1, 6, 11, 16, 21, and say 1, 6 and 11 were first. however, there may be a case where horse #2 was faster than say 11, because you're racing from different groups. think of it as a cohort grading system. you can be second in a class of a school with each cohort having say 10 classes, but you can have rank 3 in the cohort. this would mean you are better than 8 other classes of #1s, as you MUST have someone above you as you are second in your class, and that leaves one more person forced to be a #1 in another class since having a #2 above you would not make sense as that would mean 3 people at minimum above you in ranking, meaning you at best #4.

Jase Jason
- 4 years, 4 months ago

yes great explanation

Deepanshu Thakur
- 7 years, 1 month ago

Many solutions give the construction for
$7$
races, but none of them gives the proof of why
$6$
races are not enough, so here we go. Throughout this proof, the
*
winner
*
is the horse that is the fastest among all 25, and a horse is
*
eliminated
*
if it can no longer be the winner.

On every race, we can only eliminate $4$ horses. Since there are $25$ horses, we need to eliminate $24$ of them, so we need at least $\frac{24}{4} = 6$ races.

Now, suppose that we can determine the top three in $6$ races. Note that by our observation above, the last race must be the race that determines the winner; if the winner has been determined before $6$ races, then we wouldn't need $6$ races. Also, clearly we cannot do a race containing a horse that has been eliminated before, since the bound is tight; if we don't eliminate $4$ horses in each race, we won't eliminate all $24$ horses in $6$ races. So any of the horses racing in the last race might win.

Also, note that one of the horses in the last race must have raced before; after each race, one horse still has chance to win, and the $20$ horses not participating in the last race have been eliminated, so the winner of the fifth race must be among these five. Denote $A$ as the winner of the fifth race, $B,C,D,E$ as the remaining horses in the last race, and $F$ as the second placer of the fifth race (beaten by $A$ ).

Consider the worst case where $A$ wins the last race; for clarity, suppose $B,C,D,E$ also finish in that order so that $B$ is the second finisher of the last race. Now we cannot tell which horse is the second fastest; either $B$ or $F$ might be the second fastest, as they win against all horses they race against except $A$ . So we cannot guarantee we get the second placer with just $6$ races, much less all top three.

Thus we have shown $\boxed{7}$ races are necessary, and as others have shown, are also sufficient.

18 Helpful
0 Interesting
0 Brilliant
0 Confused

nice explanation :)

Sudipta Paul
- 7 years, 1 month ago

so what we have to find is actually the 1st,2nd,3rd placing but not top 3 ???

Jonathan Moey
- 5 years, 6 months ago

Log in to reply

This was my question as well. With no timing device there is no guarantee that the entire first group isn't running faster than the fastest horse in the second group.

John Mason
- 5 years ago

Log in to reply

That's why you later compare the fastest horses from all groups to figure out the actual fastest horse, and then you apparently can arrange one more race to figure out the second and third fastest horses.

Ivan Koswara
- 5 years ago

Divide the 25 racehorses into 5 groups (A,B,C,D,E) and have each group race to determine the 1st, 2nd and 3rd from each group.

Create another group(Group F) containing all who placed first in the previous races. Have them race and the one who placed first here is the fastest of them all.

Finally, create another group (Group G) containing the 2nd and 3rd from Group F 2nd and 3rd from the group where the fastest racehorse came from, and the 2nd from where the 2nd place from Group F came from. The 1st and 2nd placers in this race will be the 2nd and 3rd fastest of them all respectively.

All in all,
**
7
**
races.

5 Helpful
0 Interesting
0 Brilliant
0 Confused

Still need a proof that 6 races are not enough.

Ivan Koswara
- 7 years, 1 month ago

I thought it was only 6 XD I did not consider the chances that the other set's second place can beat the other sets' first places.

Ferriel Melarpis
- 7 years, 1 month ago

this is the right logic.. it was my logic too...

Sudipta Paul
- 7 years, 1 month ago

I think minimum 8 races is required to identify the top 3 winners...1st, 2nd & 3rd... How-?? I m explaining here... Make 5 grps A, B, C, D & E...and make them race(5 races) Winner of each grp would have 5 horses so form another grp F and make them race (6th race) Winner of grp F will be the 1st placer amongst all 25 horses. Now...remaining 4 horses left in grp F...Once again make them race(7th race)...winner will be the 2nd placer amongst 25 horses Finally...3 horses left in grp F...Make them race(8th race)....winner will be the 3rd placer amongst the 25 horses

Santosh Behera
- 6 years, 12 months ago

Set the 25 horses as a-y
The winner of each group is the first letter of that group of horses, the secone letter stands for the second place, and so on.

The solution for this question is:

Race in 5 groups: Abcde fghij klmno pqrst uvwxy

First place race: Afkpu

Second and third: bcfgk

2 Helpful
0 Interesting
0 Brilliant
0 Confused

why can't the 2nd place of afkpu also be the second overall?

Log in to reply

After having the 7th race (bcfgk) , then you will know if "f" is the second place or the other competitor is. "f" can possibly be the second place, so as the second place "b" in (abcde). Basically, "f and b race" is the second place race, and " c, g, and k race" is the third place race.

A Former Brilliant Member
- 7 years, 1 month ago

Log in to reply

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

We draw a diagram, representing the horses that won from left to right, after running races on each horse, 5 at a time.

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

Hence, we can cross out the last two in each row. Racing the winners in each row, we can then list them from top to bottom again.

1 2 3

6 7 8

11 12 13

16 17 18

21 22 23

Note that now we have 6 races, because we raced 1, 6, 11, 16, and 21 then reordered them, finding 1 to be the fastest and 21 the slowest. Hence, 16 and 21 and everything that lost to them is out.

1 2 3

6 7 8

11 12 13

We can also remove 12 and 13 (must be behind 11, which is third place at best). We can also remove 8 (must be behind 6 and 7, but 6 is second at best)

1 2 3

6 7

11

We already knew 1 was the fastest, so we only need to race the last 5 to find who is the second and third fastest. Hence, we are done in 7 races.