Author |
Topic: Minimum races problem (Read 1140 times) |
|
Naumz
Newbie
Rule over your dreams. Don't be ruled by them.
 
Gender: 
Posts: 17
|
 |
Minimum races problem
« on: Aug 26th, 2006, 6:34am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
 |
Re: Minimum races problem
« Reply #1 on: Aug 26th, 2006, 12:05pm » |
Quote Modify
|
I assume that unlike real horses, performance does not vary from race to race.
(1) is easy: | hidden: | 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. |
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Naumz
Newbie
Rule over your dreams. Don't be ruled by them.
Gender:
Posts: 17
|
|
Re: Minimum races problem
« Reply #2 on: Aug 27th, 2006, 10:49pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Minimum races problem
« Reply #3 on: Aug 28th, 2006, 4:52am » |
Quote Modify
|
2) I think 9 races suffice.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Minimum races problem
« Reply #4 on: Aug 28th, 2006, 9:09pm » |
Quote Modify
|
| hidden: |
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.
|
|
| « Last Edit: Aug 28th, 2006, 10:24pm by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Minimum races problem
« Reply #5 on: Aug 28th, 2006, 10:00pm » |
Quote Modify
|
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:
| hidden: |
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.
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2874
|
|
Re: Minimum races problem
« Reply #6 on: Aug 29th, 2006, 9:58am » |
Quote Modify
|
on Aug 28th, 2006, 9:09pm, Deedlit wrote:| hidden: |
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.
|
|
|
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...
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Minimum races problem
« Reply #7 on: Aug 29th, 2006, 10:03pm » |
Quote Modify
|
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)
| hidden: |
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.
|
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Minimum races problem
« Reply #8 on: Aug 30th, 2006, 8:42am » |
Quote Modify
|
on Aug 29th, 2006, 10:03pm, 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...
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Minimum races problem
« Reply #9 on: Aug 30th, 2006, 6:34pm » |
Quote Modify
|
on Aug 27th, 2006, 10:49pm, 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).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print