|
edit: please put the total number of races in your solutions, it's a pain to count lol
Phew it's been awhile, but since finals are over I can start posting some more.
Last time's puzzle was first solved by Valkynaz or Muirhead(2nd but with a clearer explanation), good job!
+ Show Spoiler [solution] +
Use Muirhead's solution, it's more intuitive than the one I have in mind.
Today's puzzle would be abit simpler, and here it is:
You have 25 horses, each has a different speed, you can race them 5 at a time. You can only tell the speed of the horses comparatively (i.e. you cannot measure the speed of the horses, you can only see who comes in first, second, and so on...)
How many races do you need to find the top 3 horses?
Justify your answer.
Again, answers in spoilers, and attempt the problem(i.e. post something you have in mind, if you think it's not yet ready for an answer, just leave it out of the spoiler) first before opening any spoilers, you'll find the answers more illuminating that way.
Good luck!
|
+ Show Spoiler +race 5 races with 5 different horses in each. Then eliminate the slowest 2 from each race. That will leave you with 15. Now race 3 races with the top 5 from the first set, the 2nd from the first set and the 3rds from the first set. We can elimiinate the 4 runners up in the 3rds race, all but 1st and 2nd in the 2nds race, and all but the first 3 in the winners race. We know the winner of the 1sts race is the fastest. So finally we have a race with the 2nd and 3rd from the winners race, the 1st and 2nd of the 2nds race and the winner of the 3rds race. This will give us #2 and #3
|
Is it that you can race at most 5 of them at a time? And for the top 3 horses, do you necessarily need to find out the first/second/third? And what if there is a hypothetical four-way tie for first? (the problem does not assume that each horse has a different speed)
|
On May 23 2009 21:47 goldrush wrote:
(the problem does not assume that each horse has a different speed)
the problem has been patched.
|
+ Show Spoiler +My initial guess would be 9 races but this is after spending all day doing assignments so I might have missed something  I did: 5 races of 5 horses, take top 3 from each (to cover the possibility of all 3 fastest being in one group) 3 races of 5 horses; arranged so that the first from each group forms one group of 5, all 2nd place in another and all 3rd place in another. The winner of the group with all winners is definitely in the top 3. This then leaves 5 more horses to race and the top two are the others. This is because 2nd-5th in the group that all came 3rd all have at least 3 horses faster than them, the group where all came 2nd 3 of them can be rules out in this way, and in two in the first group have 3 more horses faster than them (and one is automatically faster than the others). However; it might be that you know which horses are which and you can keep on record the fact that say when you have the three groups there may be a horse in one that you know has lost to a horse already eliminated (e.g. the winner of group with all 2nd place might have come 2nd to the horse which came last in the group of all 1st, thus has at least 5 horses faster than it). If we assume this works out all nicely like that then you could get the answer with just 8 races because of a circumstance in which: Winner of 2nd group has lost to 3rd or worse in first group and winner of 3rd group has lost to one of the horses in the 2nd group obviously. so it is ruled out and in this case it would be where one of the fastest horses are in a different initial group
I hope I explained that OK, like I said I am a little bit out of it :3 will recheck my answer to see if it makes sense tomorrow xD
|
Oh I think the Irish bloke above explained it better, perhaps :3 But still my ideal situation stands.
|
+ Show Spoiler +Race all 5 sets of 5 horses. Eliminate the bottom 2 out of each group. Label each group A, B, C, D, and E.
Race the winners of each group. For simplicity I will pretend that A comes in first, B in second, and C in third. It is now completely impossible for any horse in group D/E to be in the top 3 so eliminate both entire groups.
Group C has three horses, but only the best one can possibly be in the top 3 since the winners of Group A+B were better. Eliminate all but the winner of Group C. Group B is in a similar position. B's 3rd place horse cannot possibly be in the top 3, so eliminate that one.
This left us with Group A having 3 horses, B with 2, and C with 1.
Since we know that the winner of Group A is the best horse period thanks to the winners match, we can simply race all the other 5 at once.
The first and second place of this race become the second and third best horses.
Race count:
5 - Establishing original group rankings
1 - Winner's Match
1 - 2nd+3rd placing
Total races: 7
Edited to simplify my explanation.
|
+ Show Spoiler +6 races
It takes 5 races for all the horses to be raced. All you need to do then is take the 5 winners and race them. Top 3 in the winners race are the 3 fastest in the order they finished
|
On May 23 2009 22:34 ssystem wrote:+ Show Spoiler +6 races
It takes 5 races for all the horses to be raced. All you need to do then is take the 5 winners and race them. Top 3 in the winners race are the 3 fastest in the order they finished
Sry but no. What if you happen to have the second fastest and/or third fastest in the same group with the fastest horse?
This seems interesting. My guess is somewhere around 10-15 but I have to check it out.
|
On May 23 2009 22:17 Origami wrote:+ Show Spoiler +Race all 5 sets of 5 horses. Eliminate the bottom 2 out of each group. Label each group A, B, C, D, and E.
Race the winners of each group. For simplicity I will pretend that A comes in first, B in second, and C in third. It is now completely impossible for any horse in group D/E to be in the top 3 so eliminate both entire groups.
Group C has three horses, but only the best one can possibly be in the top 3 since the winners of Group A+B were better. Eliminate all but the winner of Group C. Group B is in a similar position. B's 3rd place horse cannot possibly be in the top 3, so eliminate that one.
This left us with Group A having 3 horses, B with 2, and C with 1.
Since we know that the winner of Group A is the best horse period thanks to the winners match, we can simply race all the other 5 at once.
The first and second place of this race become the second and third best horses.
Race count:
5 - Establishing original group rankings
1 - Winner's Match
1 - 2nd+3rd placing
Total races: 7
Edited to simplify my explanation.
Ahhh mang, I think I was getting to this towards the end of mine - I should have noticed it but didn't, yeah
|
On May 23 2009 22:59 Mah Buckit! wrote:Show nested quote +On May 23 2009 22:34 ssystem wrote:+ Show Spoiler +6 races
It takes 5 races for all the horses to be raced. All you need to do then is take the 5 winners and race them. Top 3 in the winners race are the 3 fastest in the order they finished Sry but no. What if you happen to have the second fastest and/or third fastest in the same group with the fastest horse? This seems interesting. My guess is somewhere around 10-15 but I have to check it out.
Oh right damn. =/
|
+ Show Spoiler +Divide the horses into 5 groups A to E and race the groups. The winners of every group, A1, B1, C1, D1, E1 race each other. This is the sixth race, F. The horse that came in second place to the W3 horse in the first race is obviously no in the overall top 3. Same with the horses that came in third to W2 and W3 in the first race. After removing the W1 horse and the above mentioned "not as good" horses, we race the remaining 5 that might have a chance to determine the 2nd and 2rd fastest horse. Total: 7 Races
|
Got the upper bound everyone else got in the same way, but proving that one less is not possible was a little more involved (and is generalizable to similar problems), so before I post it someone point out if I've missed an obvious way
|
+ Show Spoiler +Okay. First you race all the horses, 5 groups of 5 horses each. From these groups, pick the winner, second place and third place horse from each race, now we have a group of 15 horses (5). Make a group of the winners, a group of the second places, and a group of third places and make them race. From the winners group, pick the winner, second place and third place; from the second place group, pick the winner and the second place, from the third place group, pick only the winner. Now we have excluded every horse that cannot be top 3, since in the second place group, the number 3-5 would have lost to over 3 different horses, the third place group, number 2-5 would also have lost to more than 3 different horses (3). Now we have 6 horses left. But, the winner of the winners group is the fastest horse, since it has beaten the winners of the other groups. So now we have 5 horses left, make them race, pick the winner and the second place, and you have you top 3 horses(1).
Races used: 5+3+1=9
Justifying this is the fastest solution might be tricky, will try to see if I can make an argument on contradiction or something, dunno, will wait with that.
|
+ Show Spoiler +7 races total
race 5 groups of 5
race winners of each group
race 2nd, 3rd from that prev race, along with next 2 from winner's original group and next 1 from 2nd place's original group
all possible 2nd and 3rd place horses are in this final 7th race, so it is correct
|
+ Show Spoiler +
yay sorting algorithms!!!
my guess would be 6
so you split the horses up into groups of 5 then have 5 races
take the winner of each and have the final race
of course my guess is wrong...its 9
you gotta race the 1stplace group take top two set them aside
race 2nd and 3rd place groups
take top two of the third place group and top three from 2nd place group and race them
take top three and put in race with 1st place winners and there you have it
|
+ Show Spoiler +7
Divide horses into 5 groups
I'll call the groups A, B, C, D, E
I will use X.1, X.2, etc. for first place, second place ... in group X.
Race the five groups, and this will give us A.1, B.1, ...
Race A.1, B.1, C.1, D.1, and E.1
Assuming the result of the race is A, B, C, D, E, this tells us A.1 is the fastest horse.
Race
A.2, A.3, B.1, B.2 and C.1
Done.
|
|
|
|
|
|
|
|
EPT
