25 Horses, 5 Race Tracks. How Many Races You Have to Run to Select Top 5 Horses.
Here is a problem that has been asked as an interview question.
There are 25 horses. What is the minimum number of races needed so you can identify the fastest 3 horses? You can race up to 5 horses at a time, but you do not have a watch.
As this question is a bit vague, here is a more precise version you can solve.
Interview Question (with more details)
There are 25 mechanical horses and a single racetrack. Each horse completes the track in a pre-programmed time, and the horses all have different finishing times, unknown to you. You can race 5 horses at a time. After a race is over, you get a printout with the order the horses finished, but not the finishing times of the horses. What is the minimum number of races you need to identify the fastest 3 horses?
I was suggested this problem by email from puzzle maker and speaker Terry Stickels.
This is also a classic interview question asked during programming interviews at tech companies like Google. It took me a good 10-15 minutes to figure it out. Can you figure it out? Watch the video for a solution.
Can You Solve The 25 Horses Puzzle? Google Interview Question
Or keep reading.
.
.
"All will be well if you use your mind for your decisions, and mind only your decisions." Since 2007, I have devoted my life to sharing the joy of game theory and mathematics. MindYourDecisions now has over 1,000 free articles with no ads thanks to community support! Help out and get early access to posts with a pledge on Patreon.
.
.
.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To The 25 Horses Riddle
Here is how you can find the fastest 3 horses in 7 races.
Step one
Divide the 25 horses into groups of 5, and race the horses in each group. (5 races)
Step two
Take the winner from each group and race those 5 horses. The winner of this race is the fastest horse overall. (1 race)
Notation
Label the 5 groups from step one as a, b, c, d, e to correspond to horses finishing 1st, 2nd, 3rd, 4th, and 5th in step two. Write a subscript to identify the order that the horse finished in the group, so a 2 means the horse that finished 2nd place in group a.
Step three
Do one more race with horses a 2, a 3, b 1, b 2, c 1. That is, race the second and third fastest from group a, the fastest and second fastest from group b, and the fastest from group c. The top 2 horses in this race are the 2nd and 3rd fastest horses overall. (1 race)
Why does this procedure work?
The logic of finding the fastest horse is straightforward. First the 25 horses are split into 5 groups. Any horse that loses a race cannot be the fastest overall. This eliminates 20 horses that finished in 2nd to 5th place.
Now the 5 winners race against each other. The horse that wins this race is faster than the other winners, and the other winners are faster than the other horses in their group. The fastest of the winners is therefore the fastest horse overall.
Now, how can we find the second and third fastest?
The fastest horse is denoted a 1. There is no need to race this horse again as it is identified as the fastest overall. Which horses could be the 2nd or 3rd fastest overall?
We can first eliminate all horses from groups d and e as top 3 possibilities. This is because even the fastest horses in groups d and e are slower than the three horses a 1, b 1, and c 1.
Similarly, we can eliminate every horse in group c that is slower than c 1, as those horses raced slower than the three horses a 1, b 1, and c 1.
Next we can eliminate a 4 and a 5, as they are slower than a 1, a 2, and a 3. Finally we can eliminate b 3, b 4, and b 5, as they are slower than a 1, b 1, and b 2.
We are left with 5 possible horses to test: a 2, a 3, b 1, b 2, c 1. We need to race these horses.
Here is a slightly different explanation of why these particular horses need to be raced again.
It might have been that all 3 fastest horses were in group a from the start. Thus, we have to race a 2 and a 3 once more.
Or it might have been that only the fastest horse was in group a, leaving the 2nd and 3rd fastest to be in group b. Thus we have to race b 1 and b 2 again.
Or maybe the fastest horse was in group a, the 2nd fastest was put in group b, and the third fastest was put in group c. This means c 1 is a possibility too.
This leaves 5 horses that could be the second and third fastest horses. The horses we need to race again are then: a 2, a 3, b 1, b 2, c 1.
The winner of this race is faster than every horse except for a 1, so the winner is the 2nd fastest horse overall. The second place of this race is then the next fastest horse overall, so it is the 3rd fastest horse overall.
Here is another way of saying what was just explained. Imagine the 25 horses are numbered from 1 = fastest to 25 = slowest, but we do not know which groups the top 3 horses belong to. After the first six races, we know group a has the fastest horse numbered 1, which is faster than the quickest horse in b and then c. So there are four possibilities for where 1, 2, 3 could be:
–group a could have 1, 2, 3
–group a might only have 1,2 and group b would have 3
–group a might only have 1 and group b has 2, 3
–group a might have 1, group b has 2, and group c has 3
To distinguish between these possibilities, we need to compare the 2nd and 3rd horses from group a against the second horse from group b and the fastest horse in group c.
Proof of minimality
We have shown 7 races is a sufficient (maximum) number of races. Why is it is minimum?
To find the fastest, you need to run all 25 horses at least once, and since you can only race 5 horses at a time, you need a minimum of 25/5 = 5 races. Then you need to compare the winners of these races, which means a 6th race is necessary.
To find the second fastest, you need at least 1 more race to compare a 2 and b 1 (amongst other possible comparisons), meaning 7 races is a minimum value. As we have described how 7 races is sufficient, the described procedure is optimal.
Sources
I was suggested the problem via email from Terry Stickels. This is also a very popular problem. I came across the following websites during my research to write up the problem.
https://www.quora.com/What-is-the-trickiest-riddle-you-have-been-given-or-have-given-out-at-a-job-interview/answer/Michael-Tan-6
https://www.quora.com/What-is-the-minimum-number-of-races-necessary-to-determine-your-three-fastest-horses
http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/
http://math.stackexchange.com/questions/744473/horse-race-question-how-to-find-the-3-fastest-horses
http://quiz.geeksforgeeks.org/puzzle-9-find-the-fastest-3-horses/
http://blog.dnickolas.com/2011/04/25-horses-5-lanes-no-clock-top-5-not-3.html
http://puzzles.nigelcoldwell.co.uk/fiftynine.htm
https://sites.google.com/site/idelerdennis/blog/25-horses-problem-palantir
http://www.mathgoespop.com/2012/05/run-for-the-ranking.html
http://durso.org/puzzles/horse.html
MY BOOKS
If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.
Book ratings are from June 2021.
(US and worldwide links)
https://mindyourdecisions.com/blog/my-books
Mind Your Decisions is a compilation of 5 books:
(1) The Joy of Game Theory: An Introduction to Strategic Thinking
(2) 40 Paradoxes in Logic, Probability, and Game Theory
(3) The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias
(4) The Best Mental Math Tricks
(5) Multiply Numbers By Drawing Lines
The Joy of Game Theory shows how you can use math to out-think your competition. (rated 4.2/5 stars on 200 reviews)
40 Paradoxes in Logic, Probability, and Game Theory contains thought-provoking and counter-intuitive results. (rated 4.1/5 stars on 30 reviews)
The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 4/5 stars on 17 reviews)
The Best Mental Math Tricks teaches how you can look like a math genius by solving problems in your head (rated 4.2/5 stars on 57 reviews)
Multiply Numbers By Drawing Lines This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 4.1/5 stars on 23 reviews)
Mind Your Puzzles is a collection of the three "Math Puzzles" books, volumes 1, 2, and 3. The puzzles topics include the mathematical subjects including geometry, probability, logic, and game theory.
Math Puzzles Volume 1 features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.4/5 stars on 75 reviews.
Math Puzzles Volume 2 is a sequel book with more great problems. (rated 4.3/5 stars on 21 reviews)
Math Puzzles Volume 3 is the third in the series. (rated 4.3/5 stars on 17 reviews)
KINDLE UNLIMITED
Teachers and students around the world often email me about the books. Since education can have such a huge impact, I try to make the ebooks available as widely as possible at as low a price as possible.
Currently you can read most of my ebooks through Amazon's "Kindle Unlimited" program. Included in the subscription you will get access to millions of ebooks. You don't need a Kindle device: you can install the Kindle app on any smartphone/tablet/computer/etc. I have compiled links to programs in some countries below. Please check your local Amazon website for availability and program terms.
US, list of my books (US)
UK, list of my books (UK)
Canada, book results (CA)
Germany, list of my books (DE)
France, list of my books (FR)
India, list of my books (IN)
Australia, book results (AU)
Italy, list of my books (IT)
Spain, list of my books (ES)
Japan, list of my books (JP)
Brazil, book results (BR)
Mexico, book results (MX)
MERCHANDISE
Grab a mug, tshirt, and more at the official site for merchandise: Mind Your Decisions at Teespring.
25 Horses, 5 Race Tracks. How Many Races You Have to Run to Select Top 5 Horses.
Source: https://mindyourdecisions.com/blog/2017/05/11/can-you-solve-the-25-horses-puzzle-google-interview-question/#:~:text=To%20find%20the%20fastest%2C%20you,25%2F5%20%3D%205%20races.