Puzzle time - Sorting the Horses
-
There are 25 horses in a race and your job is to determine a complete ranking of those 25 horses by their speed.
However, the racing circuit is so small that only two horses can race at a time. You don't have a stopwatch, as Jon says, so you can only observe which horse is faster.
How many races do you need in the worst case to determine the complete ranking? How about the average case?
Somebody claims that he can always determine the ranking that way with 60 or less races. Could he possibly say the truth?
-
This is just the standard sorting problem there's a whole wiki page about the methods.
-
No, it's not.
The number of horses if fixed, hence standard algorithms don't give the optimal result. Also, standard algorithms only give you upper bounds but not lower bounds.
The optimal solution is in fact at this point unknown. I believe provably optimal solutions are only known for up to 16 horses currently.
But I think I'll make the problem a bit simpler and more tractable.
-
@klaus said in Puzzle time - Sorting the Horses:
I believe provably optimal solutions are only known for up to 16 horses currently.
I looked it up. It's even worse. An optimal (minimal in the number of races) solution is only known for up to 12 horses, and this result has been established rather recently, in December 2019.
So, there would be ample room for human creativity in this task
You are right that sorting is boring and basically "solved" when considering inputs of variable size and asymptotic complexity measures. But for concrete inputs, like in my example, it's very different. Your original puzzle would also be very boring when you consider the generalized case of n horses and asymptotic bounds: the asymptotic bound would simply be "linear in the number of horses".
My last question could have been answered in the negative by an information-theoretic argument.
-
In my feeble mind, I would have 1 race 2, then 2 race 3, 3 race 4, 4 race 5,etc. to get a "semi baseline"
Once you have establish this, you would do it again with a lesser number of races and kind of pyramid it to set the rankings.
No idea how many races this would take however.
-
@taiwan_girl said in Puzzle time - Sorting the Horses:
In my feeble mind, I would have 1 race 2, then 2 race 3, 3 race 4, 4 race 5,etc. to get a "semi baseline"
Once you have establish this, you would do it again with a lesser number of races and kind of pyramid it to set the rankings.
No idea how many races this would take however.
If you'd always swap places after each race when the horses are not in order, then your algorithm is known as "bubble sorting". You'd need about 25^2 / 2 races.
-
@taiwan_girl Here's a nice notation for your strategy that doesn't require any computer code. This is your strategy when there are 6 horses. Every horizontal line represents a horse. Every connection between the horizontal lines represents a race. If the race result determines that the horses are not in order, they swap places.
As you can see, 15 races are required with that strategy.
However, the optimal strategy requires only 12 races. Can you find it?
-
@Kalus Thanks! Very thought making!
I will have to think about how to develop the 12 race scenario!!!
-
@taiwan_girl said in Puzzle time - Sorting the Horses:
@Kalus Thanks! Very thought making!
By the way, “Kalus” is Taiwanese for “shit pianist”.
When you shake someone's deep sense of self-worth, leaving a scar in their ego, they will persistently try to diminish you through petty arguments & obsessive captious criticism of your actions, just to soothe the wound.
- Nassim Nicholas Taleb
