bonanova Posted June 26, 2009 Report Share Posted June 26, 2009 In a previous horse race puzzle we were asked to find the three fastest horses from a group of 25 horses. Five horses could be raced at a time, and the determination was to be made running the fewest heats. If you have not tried solving it yet, you might find it interesting. In this puzzle, we want to rank order the speeds of five horses, [call them A, B ,C, D, E] assuming the speeds are all different. Simple enough if there are five lanes on the race track, but alas now there are only two lanes. How many head-to-head heats are required to do the task? For 2 horses, a single heat is required. For 3 horses, three heats are required in worst case. For 4 horses, it's fairly easy to determine how many heats it takes. For 5 horses, it becomes a challenge. Enjoy! Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 26, 2009 Report Share Posted June 26, 2009 Max 8 head to head races are needed to determine the order of speeds. How: First, A & B compete --- lets say A wins Then C & D compete --- lets say C wins Then A & E compete --- lets say A wins (this is the worst case - if E wins then only one more race between B & D is needed and the order would be EAC follwed by winner b/w B & D) Then B & D compete --- lets say B wins (this is the worst case - if D wins, order of ABCD is known: ACDB) Then C & B compete --- lets say B wins (the order is ABCD then or else ACBD) Then C & E compete --- E wins (this is the worst case or else order known) Then B & E compete --- if E wins, the order is AEBCD; if B wins the order is ABECD Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 26, 2009 Report Share Posted June 26, 2009 its 7 head to head races Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 26, 2009 Report Share Posted June 26, 2009 (edited) In a previous horse race puzzle we were asked to find the three fastest horses from a group of 25 horses. Five horses could be raced at a time, and the determination was to be made running the fewest heats. If you have not tried solving it yet, you might find it interesting. In this puzzle, we want to rank order the speeds of five horses, [call them A, B ,C, D, E] assuming the speeds are all different. Simple enough if there are five lanes on the race track, but alas now there are only two lanes. How many head-to-head heats are required to do the task? For 2 horses, a single heat is required. For 3 horses, three heats are required in worst case. For 4 horses, it's fairly easy to determine how many heats it takes. For 5 horses, it becomes a challenge. Enjoy! If you think of it as basically a sorting exercise (the worst case scenario is approximately (n⌈lg(n)⌉ - 2⌈lg n⌉ + 1), where n is the number of elements) sooo in this case (worst case DABCE: ): 1) Compare A, B You know AB 2) Compare AC 3) Compare BC you know ABC 4) Compare DE, you know DE Merge - 5) Compare AD 6) Compare AE 7) Compare BE 8) Compare CE Edited June 26, 2009 by tpaxatb Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 26, 2009 Report Share Posted June 26, 2009 (edited) 8 heats required. For E.g. AB,CD,AC,AE (A wins all, A is 1),CE,BE (E wins both, E is 2),CB (C wins, and is 3),BD (B wins, B & D is 4 & 5) If they hv 1 stop watch, this can be done in 3 heats, by counting the time taken for loosers... Edited June 26, 2009 by Terminator Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted June 26, 2009 Report Share Posted June 26, 2009 (edited) Since there are 120 permutations, it seems fair that 7 comparisons (2^7=128) could be enough to distinguish them. I agree with rohit, 7 are sufficient. It's tedious to list the permutations, but the general statement after (3) is a good abbreviation The first three heats, without loss of generality, are: (1)AB A wins (60) (2)CD C wins (30) (3) BD B wins (15) (At this point, we have ABCD, ACBD, CABD : with E in any location) (4) BE --(4a) B wins (7) --ABCDE, ABCED, ABECD,ACBDE, ACBED, CABDE, CABED --(5) DE ----5a) D wins (3) ----ABCDE,ACBDE,CABDE, -- --2 more to locate C against AB ----5b) E wins (4) ----ABCED, ABECD,ACBED, CABED, -- --2 more to locate C against ABE --(4b) E wins (8) --ACEBD, AEBCD, AECBD, CAEBD, EABCD, EACBD, CEABD, ECABD --(5) AE --5a) A wins --ACEBD, AEBCD, AECBD, CAEBD, --2 more locate C against AEB --5b) E wins --EABCD, EACBD, CEABD, ECABD --2 more to locate C against EAB Edited June 26, 2009 by CaptainEd Quote Link to comment Share on other sites More sharing options...
0 preflop Posted June 26, 2009 Report Share Posted June 26, 2009 but seriously I came up with 8 max and maybe less if you get lucky. 5 races to rank horses A through D A vs B C vs D winners vs each other losers vs each other 2nd round losers vs each other. then race E vs 2nd or 3rd it's your choice. and move E up or down the list from there. This will be a max of 3 more total races (E beats 3rd place, E beats 2nd place, E races 1st place). Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 26, 2009 Report Share Posted June 26, 2009 Since there are 120 permutations, it seems fair that 7 comparisons (2^7=128) could be enough to distinguish them. I agree with rohit, 7 are sufficient. It's tedious to list the permutations, but the general statement after (3) is a good abbreviation The first three heats, without loss of generality, are: (1)AB A wins (60) (2)CD C wins (30) (3) BD B wins (15) (At this point, we have ABCD, ACBD, CABD : with E in any location) (4) BE --(4a) B wins (7) --ABCDE, ABCED, ABECD,ACBDE, ACBED, CABDE, CABED --(5) DE ----5a) D wins (3) ----ABCDE,ACBDE,CABDE, -- --2 more to locate C against AB ----5b) E wins (4) ----ABCED, ABECD,ACBED, CABED, -- --2 more to locate C against ABE --(4b) E wins (8) --ACEBD, AEBCD, AECBD, CAEBD, EABCD, EACBD, CEABD, ECABD --(5) AE --5a) A wins --ACEBD, AEBCD, AECBD, CAEBD, --2 more locate C against AEB --5b) E wins --EABCD, EACBD, CEABD, ECABD --2 more to locate C against EAB D wins race 2? You're missing 3 combinations after step 3...it seems like you're missing a race to determine D's placement with A. 1) A vs B 2) C vs D 3) B vs D at this point we have ABCD, ACBD, CABD, ACDB, CADB, CDAB, with E in any location. Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted June 26, 2009 Report Share Posted June 26, 2009 (edited) D wins race 2? You're missing 3 combinations after step 3...it seems like you're missing a race to determine D's placement with A. 1) A vs B 2) C vs D 3) B vs D at this point we have ABCD, ACBD, CABD, ACDB, CADB, CDAB, with E in any location. It doesn't matter whether you call C or D the winner of heat 2, as long as the losers run in heat 3. Does this clarify? Or did I really miss a case? Edited June 26, 2009 by CaptainEd Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted June 27, 2009 Author Report Share Posted June 27, 2009 DeeGee, who I think miscounted his own solution, rohit_bd and CaptainEd all have it. Kudos! BTW there is a formula that predicts the number of races needed for up to 11 horses. If you want to waste some more time, you can analyze these cases and look at the answers below. The formula breaks down for 12 horses, predicting 29 races are needed. But this is wrong: clearly we need 30 races for 12 horses. we require 0, 1, 3, 5, 7, 10, 13, 16, 19, 22 and 26 races respectively. Do you see a pattern? [Look at the differences.] Can you derive a formula that would include 12 horses needing 30 races? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 28, 2009 Report Share Posted June 28, 2009 Does this clarify? Or did I really miss a case?It doesn't matter whether you call C or D the winner of heat 2, as long as the losers run in heat 3. I think i got it... You don't label ABCD until after heat 3 :-/ Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted June 30, 2009 Report Share Posted June 30, 2009 (edited) <snipped> The formula breaks down for 12 horses, predicting 29 races are needed. But this is wrong: clearly we need 30 races for 12 horses. The word "clearly" feels like an exaggeration Edited June 30, 2009 by CaptainEd Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted July 4, 2009 Author Report Share Posted July 4, 2009 The word "clearly" feels like an exaggeration Yeah, there wasn't a smiley for "tongue in cheek" Quote Link to comment Share on other sites More sharing options...
Question
bonanova
In a previous horse race puzzle we were asked to find the three fastest horses from a group of 25 horses.
Five horses could be raced at a time, and the determination was to be made running the fewest heats.
If you have not tried solving it yet, you might find it interesting.
In this puzzle, we want to rank order the speeds of five horses, [call them A, B ,C, D, E] assuming the speeds are all different.
Simple enough if there are five lanes on the race track, but alas now there are only two lanes.
How many head-to-head heats are required to do the task?
For 2 horses, a single heat is required.
For 3 horses, three heats are required in worst case.
For 4 horses, it's fairly easy to determine how many heats it takes.
For 5 horses, it becomes a challenge.
Enjoy!
Link to comment
Share on other sites
12 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.