wu :: forums - Print Page


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

        riddles >> hard >> Minimum races problem
        
(Message started by: Naumz on Aug 26^th, 2006, 6:34am)

Title: Minimum races problem
Post by Naumz on Aug 26^th, 2006, 6:34am

There are 25 horses and a race track on which only 5 horses can run at a time.

In the absence of any time measuring device,
1) minimum how many races are to be conducted to pick the 3 quickest horses?
2) minimum how many races are to be conducted to pick the 5 quickest horses?

Title: Re: Minimum races problem
Post by Icarus on Aug 26^th, 2006, 12:05pm

I assume that unlike real horses, performance does not vary from race to race.

(1) is easy: [hideb]7 races. First 5 races to have each horse run once. Then race the winners of those heats, and label the heats A-E based on the position the heat's winner placed in the "semifinal". So the winner of heat A also won the semifinal race. Number the horses 1-5 in each heat by the order in which they finished. So horse A1 has won both races it was in, while horse C2 came in second in its heat, and lost to the 3rd place winner of the semifinal.

At this stage A1 has shown itself fastest of all, while horses A4-A5, B3-B5, C2-C5, and all D & E horses have all shown themselves slower than 3 other horses. This leaves 5 horses still undetermined: A2, A3, B1, B2, C1. The 7th race is between them.[/hideb]

My first impression of this riddle was that it was much too simple for the hard forum. In fact I actually moved it to "Medium", but then changed my mind and moved it back. As I think about now, though, it has some correlations with the theory of partial orderings that are interesting, and much deeper than the problem statement sounds.

Title: Re: Minimum races problem
Post by Naumz on Aug 27^th, 2006, 10:49pm

I guess it was kind of silly to post it in the hard forum. My mind was totally blocked and i couldnt grasp any method, just had vague ideas. I'm still working on the 2nd part. Maybe i'll get it before anyone else posts the answer!

Thanks for the idea.

Title: Re: Minimum races problem
Post by Barukh on Aug 28^th, 2006, 4:52am

2) I think [hide]9 races[/hide] suffice.

Title: Re: Minimum races problem
Post by Deedlit on Aug 28^th, 2006, 9:09pm

[hideb]
It can be done in 8 races.

As Icarus did, let's run five races of heats, then a semifinal with all the winners of the heats. Label the heats and horses as Icarus did. For the seventh race, we will race A3, B2, C1, and two other horses, which for the purpose of simplicity we will ignore. If the three horses finish in the order A3, C1, B2, then the five fastest include A1, A2, and A3. The remaning two must come from A4, A5, B1, and C1. So the eight race will include those four, and we are done. The case C1, A3, B2 is done similarly. If B2 beats A3 and C1, the five fastest are A1, A2, B1, B2, and whichever of A3 and C1 beat the other. If the three horses finish in the order A3, B2, C1, then A1, A2, and A3 are definitely among the five fastest, and the remaning two come from A4, A5, B1, and B2. So run a race with those four to determine the remaining horses. The case of C1, B2, A3 is done similarly.

[/hideb]

Title: Re: Minimum races problem
Post by Deedlit on Aug 28^th, 2006, 10:00pm

The other half of the problem (and generally the more difficult part) is to prove that your solution is indeed optimal. That's not too hard for part 1:

[hideb]
Let G be a directed graph with 25 vertices representing the 25 horses, and an arrow drawn from horse A to horse B when you know that A is faster than B. Before the races start, there are 25 disconnected components; each race combines at most five connected components into one, so the number of connected components is reduced by at most four. To determine the m fastest horses, you need arrows from those m to the remaning 25-m, so there is only one connected component. So fewer than six races are insufficient. Six races can work if everything works out; for example, if you take the loser of each race and race it against four new horses, it is possible for the loser to beat the four new horses every time; after six races you'll have all the horses numbered from 1 to 25.

But six is insufficient in general. After five races there are at least five connected components left. At least one of the components has at least three horses in it. Call the fastest three horses from such a component A, B, and C, in order of speed. It's possible for C to be the third fastest, but to verify that you need to race C against the fastest horses from the other four components. But then if C loses that race, you'll have know way of knowing whether or not B is one of the three fastest or not.

[/hideb]

Part 2 appears to be more challenging:

If the first six races are run as Icarus outlined above, you need at least eight races to determine the five fastest in all cases. To end after seven races, the seventh would have to race all possible pairs of fifth fastest and sixth fastest horses. These include A4 and B2, A5 and B1, B2 an D1, and A2 and E1 - too many horses. I also tried running the second fastest horses in each heat for the sixth race - but then we need to run the winner of that race against all the winners of the heats. I imagine it would be reasonable to go through all possible sixth races like this - but a bigger problem is that we aren't guaranteed that racing five heats is the right way to do things. So we need some other approach for the general solution.

Title: Re: Minimum races problem
Post by rmsgrey on Aug 29^th, 2006, 9:58am

on 08/28/06 at 21:09:49, Deedlit wrote:

I don't follow your explanation - if A3 wins your 7th race, then there are 4 horses that could be 4th and 5th (A4, A5, B1, and whichever was faster of B2 and C1), and if B2 wins with A3 second, then there are again only 4 horses competing for 4th and 5th (A2, A3, B4 and B5) but if B2 wins with C1 second, then there are 6 horses competing for 4th and 5th (A2, B3, B4, C1, C2, D1) - there's no guarantee that A2 is faster than B2...

And when C1 wins, A2, C2, C3, D1, D2 and E1 could each be in the top 5, as could A3 if it placed second, or B2 and B3 if B2 placed second - up to 8 candidates...

Title: Re: Minimum races problem
Post by Deedlit on Aug 29^th, 2006, 10:03pm

Ackkk... you're right, I foolsihly got it into my head that the ordering went to the right as well as up and down. Okay, here's the fix: (er, maybe)

[hideb]
I guess we can't cavalierly overlook the other two horses in the seventh race. Let's run the horses A3, B2, C1, C2, and D1. We've already seen that when the first three horses mentioned come in any of the orders A3, B2, C1, or A3, C1, B2, or B2, A3, C1, the problem is solved. (I messed up the last case, but the only undecided horses in that case are A2, A3, B3, and B4.) In the case B2, C1, A3, the undecided cases are A2, B3, B4, C1, and whichever of C2 and D1 is faster.

In the case that C1 is the fastest, look at the next fastest horse:

If it's A3, then A1, A2, A3, B1, C1 are the fastest horses.

If it's any of B2, C2, or D1, then that horse plus A1, B1, and C1 will be among the five fastest; the fifth horse must be one of the next horses from one of the heats, which can be no more than five.
[/hideb]

Title: Re: Minimum races problem
Post by rmsgrey on Aug 30^th, 2006, 8:42am

on 08/29/06 at 22:03:01, Deedlit wrote:

Ackkk... you're right, I foolsihly got it into my head that the ordering went to the right as well as up and down. Okay, here's the fix: (er, maybe)

Looks good - and leaves me thinking I should have spotted it myself... I was trying to come up with something of the sort when I was writing up my criticisms of your earlier version...

Title: Re: Minimum races problem
Post by Icarus on Aug 30^th, 2006, 6:34pm

on 08/27/06 at 22:49:10, Naumz wrote:

I guess it was kind of silly to post it in the hard forum. My mind was totally blocked and i couldnt grasp any method, just had vague ideas.

No, the more I look at this, the more I agree that it deserves to be right where it is. It is challenging, and it has deeper implications. And it is hard because it is complex, and not because needed information is missing (the common reason people post undeserving problems in the Hard forum).