Zylon
1621
By that logic, I can do it in zero heats. Just assume the first three horses I pick at random are the three fastest.
That’ll go over real well at your hiring interview. :D
Kael
1623
The difference is that baruk has proven it by the end of his 6 heats. He just needs the heats to work out perfectly.
Release the hounds. Last one they catch is the fastest.
I think “controversial” can be replaced with a more direct word. :)
Well, both baruk and Zylon believe in their luck.
Baruk is kind enough to tell us how he can prove it in 6 races.
He just need to tell us the odds of picking 5 out of 25, and having the 3 fastest horses among them.
If you are lucky and belive in it, you need 6 races.
If you are lucky (or not) and don’t belive in it, you need 7 races.
If you believe you are lucky, but aren’t, it will take you more than 6 races.
The logic method are only satisfying on a small scale, whereas the lucky method are great fun. Instead of just taking notes for the first 5 races, you start to use/gamble with experience gained, already in second race.
If you are on a company picknick use baruks lucky solution, and in an interview use the logic one.
If you feel brave, you can ask if they want to know how fast it can be done with or without regards for the jobsatisfaction. You can tell them that regards for jobsatisfaction doesn’t always mean slower.
Honestly, if an interviewer asked this question to me, my answer would be “Eclipse, running on my laptop, could just work through every permutation of races + horse speed in the time it would take me to describe a solution, and give the absolute best possible one.”
Sometimes, being clever is unnecessary and would take more time than just using the absurdly powerful computational devices we carry around.
Yeah, but skedastic’s solution is elegant and I am glad to know it!
I’m not convinced it can’t be done in six for arbitrary arrangements of horses, though. The seven solution is pretty straightforward: it’s trivial to find the fastest horse using five non-overlapping races and a run-off for the winners. To find the next two fastest, notice that those six races rule all but five out of the top three, so you just need one more race to order those remaining five.
But perhaps it’s not optimal to run five non-overlapping heats. Each of these heats has the advantage that you get information on five new horses, but because there’s no common horses you get no ordering across races.
There may exist some clever strategy which allows you to always find the top three in six heats, it’s just not a strategy which involves first running five non-overlapping heats.
I have no solution for this problem, but I guess it’s seven: what’s the minimum number of heats required to completely rank all 25 horses?
Sometimes, being clever is unnecessary and would take more time than just using the absurdly powerful computational devices we carry around.
I think there are [ C(25,5) ]^5 different ways to run these races, which is about 10^34. If you can evaluate a trillion strategies per second, you’ll have to ask for your job interview to be extended by about 333,900,000,000,000 years while you all sit around in the interview room waiting for laptop to finish crunching numbers.
Hmm, while I agree with the logic here, I think I would argue for a 47/0/1/0/2 solution. As player 5, it is true that given the rules of the game and all participants being rational, you couldn’t expect more than 1. But it’s also true that player 5 can afford to say no up until the third iteration. As such, it would seem that a perfectly rational player would wait until that point, in case an unrevealed factor shows up. To prevent this from happening, I would offer player 5 two.
The only way I’ve used Eclipse involves using branching/decision-tree logic, which means that as soon as you run into a condition wherein all further decision subsets are invalid, you automatically prune every subset.
You can make a few simple assumptions (for example, any strategy which must involve 7+ heats to run each horse at least once is out) which should prune it down by orders of magnitude.
If by relative speed, in the description of the problem, you mean that you can ascertain that a horse A is a determinable factor faster than a horse B you can do it in six races. Run one race, put one horse as index horse and use it to index the speed of the other horses by racing it vs the remaining 20 horses 4 at a time.
What if the horse places first in every race?
I would love this to be true, because I’m sure the solution would be amazing, but I don’t think it can be true. Every horse needs to run in at least one race, or else it might be top three horse and you’d never know. That requires 5 races at least. And there’s no way to pick 1/2/3 with just one more race.
Well if we assume that the problem states not just that you can order the speed of the horses but that you can determine their relative speeds, it doesn’t really matter where the horses place in the race, since you can index their speeds visavi the index horse and thus order all of them them. And you can have one horse running vs all the others in six races. Skedastics solution is more grounded in reality of course, but if we take the problem at face value as described here it should be doable in six races. Barring I have misunderstood due to the language barrier of course.
You don’t have any way of timing them. If the index horse you chose in race 1 places, say, last to every other horse in the other races, you don’t know enough useful information to determine the placement of the 16 horses who only raced against the index horse from group 1, and group 1 itself.
I get that. But if we just use the information in the telling of the problem it says we can determine the horses relative speed, which if my grasp of english is sufficent, mean we can say horse 2 is 1.12 times as fast as horse 2, and that we can order them accordingly, comparing how fast they are compared to the index horse. I realise this isn’t very realistic but if we just use the information in the way it is provided it state that we can in fact determine their relative speeds not just that horse 1 dominates horse 2 etc… I included the caveats in the previous posts because it is a ‘solution’ that relates on how the riddle is stated rather than what would be feasible in reality.
Although I guess you could determine their relative speeds by determining by what distance they were ahead or after the index horse when the index horse crossed the finish line. Provided you had sufficently exact measurements.
It’ll never reach the third iteration. Let’s say player 1 can’t get two additional votes, and so that player is eliminated. Player 2 then proposes a division. The optimal division for player 2 is $4900 for him/herself, and $100 for player 4.
If player 5 doesn’t accept the $100 initially offered by player 1, he or she will get nothing. It’s non-optimal for player 1, knowing that all other players are perfectly rational, to offer player 5 any more than the minimum.
Ah right, I failed to account for the fact that we can rely on player 2 to give 100 to player 4 rather than 5 to avoid this very problem. I didn’t have anyone giving money to player 4, probably because he kicks puppies.
Each race has 5! possible outcomes and you need to distinguish 25! possible rankings. Since log_{5!} (25!) = 12.12, it can’t be done in fewer than 13 races.
