Author |
Topic: 3814697265625 horses (Read 1908 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
3814697265625 horses
« on: Jun 9th, 2017, 4:24am » |
 Quote  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
    
Gender:
Posts: 2873
|
|
Re: 3814697265625 horses
« Reply #1 on: Jun 9th, 2017, 11:37am » |
Quote Modify
|
step 1: 515 races to race every horse once.
|
|
IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: 3814697265625 horses
« Reply #2 on: Jun 9th, 2017, 2:07pm » |
Quote 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:
Posts: 13730
|
|
Re: 3814697265625 horses
« Reply #3 on: Jun 9th, 2017, 11:59pm » |
Quote 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
Gender:
Posts: 2873
|
|
Re: 3814697265625 horses
« Reply #4 on: Jun 10th, 2017, 4:37am » |
Quote 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:
Posts: 13730
|
|
Re: 3814697265625 horses
« Reply #5 on: Jun 10th, 2017, 7:48am » |
Quote 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:
Posts: 7527
|
|
Re: 3814697265625 horses
« Reply #6 on: Jun 11th, 2017, 7:53am » |
Quote 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:
Posts: 13730
|
|
Re: 3814697265625 horses
« Reply #7 on: Jun 11th, 2017, 9:08am » |
Quote Modify
|
Damnit.
Guess I made on off-by-one error myself somewhere. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 3814697265625 horses
« Reply #8 on: Jun 11th, 2017, 10:09am » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print