Puzzle: The horse race problem
A friend of mine from Australia sent me this problem yesterday. It turns out to be a very interesting puzzle. See if you can get it. Feel free to send in your answers or attempts in the Comments section and I will try to respond.
In a horse race, 25 horses show up to win the gold, silver and bronze medals. Unfortunately for the organizers, there are only 5 tracks available – which means you can race only 5 horses at a time. The owners/jockeys agree that their horses will have to run multiple times to decide the first, second and third ranks. You can assume that a horse can run any number of times and always retains the same speed anytime it runs.
Here is the question: What is the minimum number of races you have to have to decide the gold, silver and bronze medalist?
Answer:
As many of you have figured out the minimum number of races you have to run is 7. Here it is:
Race 1: Pick any random 5 horses. The ones that come 4th and 5th obviously can be eliminated. We keep the rest – let’s call them a1 (who came first), a2 (came second) and a3 (came third).
Race 2: Pick another 5 horses at random – race them, eliminate the 4th and 5th and we have b1, b2, b3.
We go thru this with Race 3, 4 and 5.
Now we have a1, a2, a3, b1, b2, b3, c1, c2, c3, d1, d2, d3, e1, e2 and e3.
We know within of a letter how the sequencing is but we cannot compare between the letters at all.
Race 6: Let’s race the fastest from each letters – a1, b1, c1, d1 and e1.
Say the results were d1 (fastest), b1, e1, a1 and c1.
Well a1 and c1 who came in 4th and 5th can be eliminated. Not only that, a2, a3, c2, c3 can be eliminated too. (a1 is faster than a2 and a3 from Race 1 but we had to eliminate a1 at the end of Race 6. So, a2 and a3 can never get any medal)
We are left with d1, d2, d3, b1, b2, b3, e1, e2,e3.
What else do we know?
d1: Obviously the fastest horse in the group: Gold medal
d2: faster than d3, slower than d1; know nothing else. Inconclusive.
d3: slower than d1 and d2; know nothing else. Inconclusive.
b1: faster than b2 and b3; slower than d1; know nothing else. Inconclusive.
b2: faster than b3; slower than b1 – also slower than d1 (since b1 is slower than d1); know nothing else. Inconclusive.
b3: slower than b2 and b1 – also slower than d1 (since b1 is slower than d1); Then no chance of getting a medal. Eliminated!
e1: faster than e2 and e3; slower than b1 and d1; know nothing else. Inconclusive.
e2: faster than e3; slower than e1 – also slower than b1 and d1 since both beat e1 in Race 6; Then no chance of getting a medal. Eliminated!
e3: slower than e2 and e1 – also slower than b1 and d1 since both beat e1 in Race 6. Then no chance of getting a medal. Eliminated!
The above might be easier if you follow Ashish’s instruction and write it in rows and columns.
So, we are left with d1, d2, d3, b1, b2 and e1. Of which d1 got the gold medal. So, we are left with 5 horses – d2, d3, b1, b2 and e1.
We need to race them for one last time Race 7. That will tell us the silver and bronze medalist!