Morris: A Day at the Races
25 horses have entered your race meeting. You have to award ribbons to the three fastest, in order.
Only five horses can compete in one race.
Assuming each horse always runs at the same pace, and that all 25 horses have different abilities, what is the fewest number of races you can use?
You can’t use stopwatches, you can only use the finishing order of each race.
UPDATE: Thanks for all the great comments. At the time of writing we’ve had three correct answers; Mike and Blaise in the comments and Jim via email.
I have a follow up question: can you prove that this answer is minimal? There is a neat spot, can you find it?
Apparantly this was an interview question for Facebook. I found it in this list of impossible interview questions. Math Factor afficionados will recognise some of these problems and not find them so impossible. Have fun!
http://skymcelroy.tumblr.com/post/6244020081/impossible-interview-questions-from-facebook-goldman
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Sue VanHattum said,
July 4, 2011 at 8:07 pm
Nice one! Do you want answers here?
Stephen Morris said,
July 4, 2011 at 8:16 pm
Sue (and everyone),
Yes please post your answers here. However use the spoiler tag if you think you have the actual answer. No need if it’s just thinking it through.
Spoiler tags are [ spoiler ] my brilliant answer [ /spoiler ]
Remove the spaces in the tags, I had to include them or the system would have treated it as a proper use of spoiler tags.
Blaise Pascal said,
July 4, 2011 at 9:53 pm
(SPOILER — probably wrong, but a decent attempt anyway) [spoiler] I can do it in 7 races, 5 heats of 5 and 2 runoffs. The first 5 races yield 5 horses which could be 1st, 2nd, or 3rd, 5 horses which could be 2nd or 3rd, and 5 horses which could be 3rd (and 10 horses which are definitely not 1st, 2nd, or 3rd). For the 6th race, run all the winners of the 5 heats. Let’s call the first three finishers Able, Baker, and Charlie. Able is the fastest horse over all. We can’t tell if the 2nd pace finisher in Able’s heat or Baker is 2nd fastest yet. Every other horse has either lost to one of these two contenders for 2nd place, or lost to a horse that lost to one of them, so can’t be 2nd fastest. Likewise, Charlie, or the horse that came in 2nd to Baker, or the horse that came in 3rd to Able, are all possible contenders for 3rd. Every other horse is definitely slower than at least one of those three. So the 7th race is between the 2nd and 3rd finisher in Able’s heat, the 1st and 2nd finisher in Baker’s heat, and the 1st place finisher in Charlie’s heat. The winner of that race is the 2nd fastest, and the 2nd place finisher is 3rd fastest.[/spoiler]
rmjarvis said,
July 5, 2011 at 1:59 am
Interesting. Fewer races than I’d guessed right off the bat.
[spoiler]
You only need 7 races.
First, race 5 heats of 5 horses each.
Then race the 5 winners against each other.
Let’s call the 5 heat winners A1, B1, C1, D1, E1 in the order that they finished the 6th race.
Then, A1 is necessarily the fastest horse, since every other horse has either lost to her or to a horse who’s lost to her. So we just need to determine the 2nd and 3rd place horses.
The contenders are:
A2, A3 (the 2nd and 3rd place horses in A1’s original heat)
B1, B2
C1
A2 and B1 are the only possible horses for second place, and the other one of these two plus the other three listed above could be the third fastest.
So, race these 5 in the 7th race to determine who is 2nd and 3rd.
[/spoiler]
Sue VanHattum said,
July 5, 2011 at 10:25 am
Just testing the spoiler tag.
[spoiler]
And I thought it was 9. I thought I had to have all the second place horses run against each other, and all the 3rds. Then I ended up with the same last race. Now your solutions (BP and RMJ) make total sense to me.
[/spoiler]
Stephen Morris said,
July 12, 2011 at 2:35 pm
This is my proof that the solution is minimal. Try to find a proof yourself first.
[spoiler] With six races we can determine the fastest horse (lets call it A) but we cannot guarantee finding the second fastest (lets call it B). Suppose that we succeed in finding A. 24 horses must lose a race (that is finish second or lower) so that we know they aren’t the fastest. With six races there are only 24 opportunities to do this, so each horse loses precisely one race. This is the pigeon-hole principle. It is possible that the first race includes A but does not include B, and that some other horse, say C, finishes second. C has lost to A, so we know it isn’t the fastest, but it does not lose any other race so we will never find out that it is slower than B. We cannot rule out C as the second fastest horse and so we cannot identify that B is the second fastest. [/spoiler]
Brock Hauser said,
December 2, 2011 at 3:51 pm
11 races, the three fastest from the first race compete in the second. The three fastest from the second compete in the third and so on, in 11 races you have the three fastest and the 22 other horses cycle in behind in the others.
sohbet said,
February 6, 2013 at 10:38 am
three fastest from the first race compete in the second. The three fastest from the second compete in the third and so on, in 11 races you have the three fastest and the 22 other horses cycle in behind