wu :: forums
« wu :: forums - 3814697265625 horses »

Welcome, Guest. Please Login or Register.
Sep 25th, 2018, 10:44am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: towr, Grimbal, Icarus, ThudnBlunder, Eigenray, SMQ, william wu)
   3814697265625 horses
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: 3814697265625 horses  (Read 514 times)
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
3814697265625 horses  
« on: Jun 9th, 2017, 4:24am »
Quote Quote Modify Modify

You have 3814697265625 (518) 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.)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: 3814697265625 horses  
« Reply #1 on: Jun 9th, 2017, 11:37am »
Quote Quote Modify Modify

step 1: 515 races to race every horse once.
IP Logged
dudiobugtron
Uberpuzzler
*****





   


Posts: 713
Re: 3814697265625 horses  
« Reply #2 on: Jun 9th, 2017, 2:07pm »
Quote Quote Modify Modify

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.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: 3814697265625 horses  
« Reply #3 on: Jun 9th, 2017, 11:59pm »
Quote Quote Modify Modify

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 518 numbers, and you can compare/sort 125 at a time, how many comparisons do you need to find the top 5?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: 3814697265625 horses  
« Reply #4 on: Jun 10th, 2017, 4:37am »
Quote Quote Modify Modify

If I've worked this out correctly, then it's (at most) 111113125 races:
 
hidden:

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.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: 3814697265625 horses  
« Reply #5 on: Jun 10th, 2017, 7:48am »
Quote Quote Modify Modify

I think/hope you overcounted by one.
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=racesizeD, #races = (#contestants-1)/(racesize - 1) + 1 .. If I got that right.

« Last Edit: Jun 10th, 2017, 11:45am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7408
Re: 3814697265625 horses  
« Reply #6 on: Jun 11th, 2017, 7:53am »
Quote Quote Modify Modify

rmsgrey looks right to me.

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).

« Last Edit: Jun 11th, 2017, 8:00am by Grimbal » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: 3814697265625 horses  
« Reply #7 on: Jun 11th, 2017, 9:08am »
Quote Quote Modify Modify

Damnit.
Guess I made on off-by-one error myself somewhere. Sad
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: 3814697265625 horses  
« Reply #8 on: Jun 11th, 2017, 10:09am »
Quote Quote Modify Modify

My first attempt at solving did come up with 1 fewer races - then I realised I was missing a bunch of horses...
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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