

Title: 3814697265625 horses Post by towr on Jun 9^{th}, 2017, 4:24am You have 3814697265625 (5^{18}) horses (really, really tiny horses), and you want to find the 5 fastest ones. You can race at most 125 at a time, how many races do you need to find the fastest 5? (If you want to start off easier, you can try the google interview version with 25 horses and find the top 3 by racing 5 at a time.) 

Title: Re: 3814697265625 horses Post by rmsgrey on Jun 9^{th}, 2017, 11:37am step 1: 5^{15} races to race every horse once. 

Title: Re: 3814697265625 horses Post by dudiobugtron on Jun 9^{th}, 2017, 2:07pm Similar to that other question, I assume that we can't directly measure the horses' speed for ourselves (I guess because they are so tiny), but that we can rely on the horses in a race to accurately order themselves in terms of speed. 

Title: Re: 3814697265625 horses Post by towr on Jun 9^{th}, 2017, 11:59pm Ah, yes. Thanks. I should have specified that. You only get the order from the races, not the absolute speed; and the performance of the horses is constant (or at least the relative order in the whole population remains the same, so no noticeable exhaustion from running multiple races etc) In the abstract, you have 5^{18} numbers, and you can compare/sort 125 at a time, how many comparisons do you need to find the top 5? 

Title: Re: 3814697265625 horses Post by rmsgrey on Jun 10^{th}, 2017, 4:37am If I've worked this out correctly, then it's (at most) [hide]111113_{125}[/hide] races: [hideb] Run a standard singleelimination tournament to find the fastest horse in 6 rounds. That fastest horse has raced 6 races, giving 6 horses that have only lost to that horse, 1 per round. Between the horses that have come 3rd to the winner, and those that have come 2nd to the ones that have only lost to the winner in various rounds, there are 21 horses with only 2 horses known to be faster than them  1 in the final, 2 in the 5th round, 3 in the 4th round, etc Between horses that come 4th to the winner, 3rd to the 2ndplace candidates, or 2nd to another 3rdplace candidate, there are 56 that have 3 horses known to be faster  1 from the final, 3, 6, 10, 15, 21 from the earlier rounds. There are then 126 further candidates for 5th place by a similar calculation, so you can't resolve the top 5 places in a single race. However, you can settle the top 4. That leaves you with 27 candidates for 5th overall  the horse that finished immediately behind the overall 4th place in each race they were in (any other horse that finished immediately behind one of the top 3 in the heats was in the top4 race so has been eliminated from the top 5). So there's the singleelimination heats and 2 runoffs to find the rest of the top 5. [/hideb] 

Title: Re: 3814697265625 horses Post by towr on Jun 10^{th}, 2017, 7:48am I think/hope you overcounted by one. [hide]I had planned there should only be one extra race after the six rounds. There should be 126 candidates for the top 5, with the 126th horse being the overall winner, who therefor doesn't need to race. It's basically just a higher dimensional version of the original version; instead of triangular numbers (2D) we go past tetrahedral numbers (3D) and two dimension further to whatever you call a hyperpyramid in 5D. You can easily solve the general case for all dimension. Given dimension D and wanting topN, racesize=Choose(N+D1,D)1, #contestants=racesize^{D}, #races = (#contestants1)/(racesize  1) + 1 .. If I got that right.[/hide] 

Title: Re: 3814697265625 horses Post by Grimbal on Jun 11^{th}, 2017, 7:53am rmsgrey looks right to me. [hide] You would need 5 elimination races to come out with 126 candidates and one final race. You would start with 5^15 horses. According to my calculations starting with 5^18 horses you end up with 84 horses for the first 4 places and 210 for the fifth place after the elimination rounds. 2 more races are necessary to bring it down to five. But it is probable that the first final race, with all rank2 to rank4 candidates, settles the matter. The only possibility for a rankfive candidate to get in the top five is when the 4 horses that are proven faster also make the top five. This is an unlikely situation. For instance if any two rank2 candidates or any two rank3 candidates are in the top four, then the rank5 candidates are automatically elimiated. Now to compute the actual probabiliy is a bit harder... (def: I call "rankn candidate" a horse that has n1 horses proven faster, by direct or indirect raking in elimination races, and can therefore hope to be nth at best). [/hide] 

Title: Re: 3814697265625 horses Post by towr on Jun 11^{th}, 2017, 9:08am Damnit. Guess I made on offbyone error myself somewhere. :( 

Title: Re: 3814697265625 horses Post by rmsgrey on Jun 11^{th}, 2017, 10:09am My first attempt at solving did come up with 1 fewer races  then I realised I was missing a bunch of horses... 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 