Ronzii's Blog

Just your average geek's blog

25 Horses

Problem: Let’s say that you have 25 horses, and you want to pick the fastest 3 horses out of those 25. In each race, only 5 horses can run at the same time. What is the minimum number of races required to find the 3 fastest horses without using a stopwatch?

Solution:
7 races should do the job. Lets assume a1, a2, a3, a4, a5, b1, b2, b3, b4, b5, c1, c2, c3, c4, c5, d1, d2, d3, d4, d5, e1, e2, e3, e4, e5 are the horses belonging to five groups a, b, c, d, e.
First race all 5 individual groups: 5 races
Now assume a1, a2, a3, b1-b3, c1-c3, d1-d3, e1-e3 are the top 3 in each group in the same order(a1 – fastest).
Now race a1, b1, c1, d1 and e1 – 1 race -> this should give us the fastest horse in all. Assume a1 – is fastest. Eliminate a1 from the group. Next assume b1 – 2nd, c1- 3rd, d1- 4th, e1- 5th in this race. So this eliminates d1, e1 and d2,d3,e2,e3 from the race.
Now we need to race a2,a3,b1,b2,c1 – last race. Here the top two horses would be second and third respectively.

So 7 races will do.

Advertisements

July 26, 2011 Posted by | Brain Teaser | | Leave a comment