firstly 5 races are required, because if even one horse is not used, this horse maybe the fastest and so the result will not be correct.
with the following steps, 7 races are enough and so the question becomes "will 6 races or even 5 races enough?" 1. group the horses 5 by 5, and suppose the result is a1 < a2 < ... < a5 b1 < b2 < ... < b5 ... e1 < e2 < .. < e5 (here < means slower than) 2. group a5,b5,..,e5 into a race, suppose the result is a5 < b5 < c5 < d5 < e5 3. now the only candidates are e5 (the fastest), e4, e3, d5, d4, c5 4. group e4, e3, d5, d4, c5 into a race and pick the fastest two horse, support they are x, y 5. then the fastest 3 horses will be e5, x, y On Thu, Nov 5, 2009 at 6:05 PM, eSKay <catchyouraak...@gmail.com> wrote: > There are 25 horses and you need to figure out the three fastest > horses by placing them into races. Assume there is no tie in the > speed. There are five tracks so for each race, you can place five > horses and figure out the relative rank among those five horses but > you don't have the exact finishing time, i.e. there is no direct > comparison between results from two different races. What's the > minimum number of races you need to arrange in order to figure out the > three fastest horses? > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
