wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Finding the Top 3 in a Horse Race 
        
(Message started by: goozer on Feb 7^th, 2005, 1:32pm)

Title: Finding the Top 3 in a Horse Race
Post by goozer on Feb 7^th, 2005, 1:32pm

Had an interview question like this, but couldn't get it in the time limit, but still interested in teh answer (i dunno it maybe pretty easy, but just can't get a elegant way of doing it with a few number of races), please help.

You have 25 horses and want to know which are the 3 fastest. Whenever you race horses, the order of finish accurately reflects the relative speeds of the horses but you can only race 5 at a time. What's the minimum number of races required to determine the 3 fastest, and how do
you do it?

Title: Re: Finding the Top 3 in a Horse Race
Post by John_Gaughan on Feb 7^th, 2005, 1:56pm

The easy way is to race five races, writing down the times, and sorting the list. I suppose we can only measure their relative speed, making it a few more iterations. I get [hide]12[/hide] races, but I do believe there is a more optimal solution...

Title: Re: Finding the Top 3 in a Horse Race
Post by Grimbal on Feb 7^th, 2005, 2:13pm

I am sure I have seen this here before.

Anyway, here is the solution: (ctrl-A to view)
::[hide]
Race all the horses in 5 races. Then, race the five winners.
Call A1 the winner of the winner's race, B1 the second and C1 the third. Call A2 and A3 the followers of A1 in his first race and B2 the second in B1's first race.
You have (X<Y means "X is faster than Y"):
A1<A2<A3, B1<B2 and A1<B1<C1

All other horses are slower than one of A3, B2 or C1, and these 3 have each at least 2 horses in front. Therefore, the top 3 are among the six horses A1, A2, A3, B1, B2, C1.

You already know who is the fastest. It is A1. To find number 2 and 3, you just need to race the remaining five.[/hide]::