wu :: forums - Print Page


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

        riddles >> medium >> 3814697265625 horses
        
(Message started by: towr on Jun 9^th, 2017, 4:24am)

Title: 3814697265625 horses
Post by towr on Jun 9^th, 2017, 4:24am

You have 3814697265625 (5¹⁸) 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¹⁵ 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¹⁸ 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₁₂₅[/hide] races:

[hideb]
Run a standard single-elimination 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 2nd-place candidates, or 2nd to another 3rd-place 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 2-7 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 top-4 race so has been eliminated from the top 5).

So there's the single-elimination heats and 2 run-offs 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 hyper-pyramid in 5D.

You can easily solve the general case for all dimension.
Given dimension D and wanting top-N, racesize=Choose(N+D-1,D)-1, #contestants=racesize^D, #races = (#contestants-1)/(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 rank-2 to rank-4 candidates, settles the matter. The only possibility for a rank-five 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 rank-2 candidates or any two rank-3 candidates are in the top four, then the rank-5 candidates are automatically elimiated.

Now to compute the actual probabiliy is a bit harder...

(def: I call "rank-n candidate" a horse that has n-1 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 off-by-one 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...