A friend of mine sent me this little puzzle, which, truth be told, did not take me long to solve.

Since today shapes up as another really busy day at work, I decided to take an easy route out of blogging and post the puzzle here. Anyone who cares to post the solution – with an explanation – in the comments thread is afforded a humongous doze of satisfaction (but no other valuable prizes). Failing anyone who has an intellect as formidable as mine, I’ll post the solution comment in a couple of days.

- There are 25 horses and a 5-track racing ring so the horses can run only 5 at a time.
- You don’t have any timers, you can just watch the finish line and record the order in which the horses arrive.
- Assume there are no ties.
- Also assume that the each horse’s speed always stays the same, no matter how many times you run them.

**PROBLEM:** What is the *minimal number of runs* you need in order to pick 3 fastest horses?

I figure 6 tries. On the first 5 tries you find out the fastest 5 horses of the 5 original groups. On the next try you should be able to find out which 3 of the 5 fastest group horses are the fastest.

Then again, you are the math genius in the family.

Kostyan, you get the prize for putting up the 1000th comment on my blog, but your answer is incorrect.

Because you do not have the timings, you have no assurances that the horse that places or shows in any given heat is, in fact, slower than the horse the wins some other heat. In theory, the three fastest horses can all find themselves in the same heat, and in your solution, you will discard two of them.

It would be too simple if it was solved as you suggest, no?

I like simple. 🙂 The question was minimal. Therefore a certain probability exists, that the fastest horse in each heat, is in fact faster than slower horses in other heats 🙂 Let’s say that it’s not 100% certain.

But I like simple, remember the fuzzy logic? Sometimes the answer is good enough 🙂 I will take the 1000th comment prize though!

My first reaction was akin to Kisintin’s guess, but I quickly corrected myself with the exact logic you state in your reply.

Hence, I haven’t got a clue how to proceed.

I think the answer is 12 runs.

The key to my logic is that the last two horses in any run cannot ever be in the top 3 overall. Thus:

First 5 runs eliminate 10 leaving 15.

Next 3 runs (15/5) eliminate 6 leaving 9.

Next 2 eliminate 3 leaving 6.

Next 1 eliminates 2 leaving 4.

Last 1 – the decider.

Sashka, your underlying logic is exactly right and you arrive at the correct number of runs needed in this case… Except, that it is not the right answer 🙁

Kostyan, fuzzy logic is good, but not in my neck o’ the woods 🙂

The answer is eleven.

Race #1: 5 horses run, three are the “fastest three”

Race #2: The fastest three race against two new competitors. The top 3 from that race are the new “fastest three.”

Race #3: Another two new competitors.

etc.

etc.

Race #1 uses 5 “new” horses. Each subsequent race uses 2 “new” horses. So you need 10 subsequent races to get through the other 20 horses. 1+10=11. QED.

How did I do?

OK, so my 90 second solution is wrong. What else is new? Back to the drawing board for another crack at it.

That’s my answer, Brian, so your prize is the contentment of knowing that you did just as well as I did. I did not see the “official” answer anywhere, I just have a big enough ego to assume that the best solution to a logical problem that I can come up with is the right one. 😛 Not that I’ve never been wrong or anything…

The key logical concept was voiced by Sasha: Each run eliminates two horses from the contention. And since we need to eliminate 22 horses in total, we need 11 runs. How to arrange that is correctly described by Brian.

The downfall of the straight-forward “playoff” system is the number of horses left after the second round. Because you have 9 – which is not a multiple of 5 – you end up having to have a heat at which only one horse gets eliminated, which causes an additional 12th run afterwards. However, if you were to switch to the same methodology at this point as described by Brian, you would whittle down 9 remaining contenders to 3 fastest in just 3 more runs. Which brings your total to 11, rather than 12, but still not better than that.

Now, just because I thought of it, let’s attempt something cleverer.

After the first heat, when you have your initial claimants for the three fastest, if you took the third-place finisher (let’s call it H3) and ran it against 4 new contenders, you theoretically can eliminate 4 horses in one shot if H3 wins its next heat. You could then theoretically repeat it just 4 more times to eliminate all remaining horses, as long as H3 keeps beating out other contenders.

Only 6 runs in the very best-case scenario! If only the question was framed as “What is the minimal number of runs you

mightneed in order to pick 3 fastest horsesif you were incredibly lucky?”Because, see, the probability that you select the three fastest horses to run in the very first heat is around .000435, and in all other 99.9565% cases there will be horses faster than at least one of your initial trio. In your worst-case scenario, H3 will only come fourth or fifth in its very next heat, allowing you to eliminate just two more horses. You end up with having run 9 horses in two heats and identifying 5 horses with a claim to be in the fastest trio. In other words, you have eliminated just 4 contenders. Which is the same number of eliminated horses after two heats if you approach the decision process with the methodology described by Brian.

We can postulate that if you stick with the approach of trying to eliminate 4 horses at a time by running new contenders against only the perceived slowest horse from among those with an established claim to be one of the fastest, you will need no less than 6 and no more than 11 runs. We are now getting into a level of probability analysis for which I certainly do not have spare time, but my educated guess is that the distribution is not normal and there is at least a .5 probability that you will get your fastest trio after precisely 11 runs, no matter how clever you are in structuring your trials. Because I’m pragmatic if nothing else, I take that as the validation of the answer that I arrived at through simple logic.

If my friend who sent me the puzzle decides to send me the answer and it turns out to be something different, I will make sure to post it here as well.

And now, I need to let my brain to cool down. What better opportunity than an interminable business meeting!

I can’t give the statistics answer (I made my way through college statistics by brute-force applying what seemed to me as logical ways of answering a question, until I got to an answer that made sense. You’d be amazed how often it works, and how Excel’s ability to do a simple task 10,000 times encourages such behavior).

Anyway, let’s call the winners of the first race horse #1, horse #2 and horse #3 (in order of finish). Say you took horse #3 and ran it against four new competitors. If it won, you’ve eliminated four horses in one race instead of two. If you went back to my proposed solution after that, you’d end at 10 races, not 11.

If horse #3 came in second, then you can use the winner of that race as your new “#3 horse” and go back to the old method – eliminating two horses per race. Again you end with 10 races.

If horse #3 comes in third, then your next race must be horse #1, horse #2, the two horses that beat #3, and one new horse, which means you only eliminate 1 horse in the next race, putting you back on track at 2 horses (on average) per race. So, you’re back to 11 races.

If horse #3 comes in fourth, then your next race must be horse #1, horse #2, and the three horses that beat horse #3, which means you eliminate zero new horses in that race. Again, 11 races.

If horse #3 comes in fifth, then you’ve lost ground – now you need an additional race to determine if the fourth place finisher is faster than horse #2 before you start eliminating new horses again. Depending on how this goes, you’re over the 11 race mark.

So, I’ll revise my answer: since four of five possibilities above leave you no worse off (and sometimes better), I’d suggest you run the third place finisher of each race against four new horses, and then go back and take the appropriate action (as above) based on the results. You can continue to employ this strategy (as opposed to doing it only once, as described above) until you’ve got a final three. Since 80% is greater than 50%, you’ll likely wind up under the 11 mark, but there’s a (20% x # of races you run) chance that you’ll go over 11.

In other words, 11 is a guarantee. If you’re willing to risk a 20% (or better) chance of failure, you can get as low as 6 (horse #3 beats four horses five times in a row). As Ilya points out, though, the odds of that happening are .0435%.

OK, now we’ve officially spent too much time on this. 😉

The truth is, Brian, we are both quite wrong. Only I am wrong all by myself, and you might have been led to adopt an incorrect approach because of my comments on Kisintin’s and Sasha’s proposals.

Applying principles of combinatorics, you can find the three fastest horses in precisely 7 runs.

Sadly, my ego gets sufficiently deflated because I had the solution pointed to me, rather than finding it myself.

You start with running 5 heats of 5 horses each. No elimination yet, just ordering – even though we can safely assume that the last two finishers in each heat cannot be among the three fastest, we simply do not have to do that yet.

Then, let’s run only the winners of each heat against one another.

That’s what Kisintin offered, although he thought it would be the end of it. I reasoned that you cannot ensure that a fastest horse in one of the heats is necessarily faster than the second or the third finisher of another heat. While that reasoning by itself is correct, it led me to erroneously dismiss the approach altogether. But in fact, after this 6th run – let’s call it the “semifinal” for the sake of simplicity – we can logically both declare the top horse

andeliminate 19 other horses.The fifth-fastest horse in the semifinal cannot be one of top three. Nor can any other horse in its original heat, obviously, as they are even slower. 5 horses eliminated.

Same for the fourth-fastest horse in the semifinal. 5 more horses are eliminated.

The third-fastest horse in the semifinal – call it S3 – can potentially be the third-fastest overall. But none of the other horses in its original heat have a claim anymore. 4 more horses are eliminated.

The second-fastest horse in the semifinal – call it S2 – still has a good claim. Only one horse is proven to be faster than it, so far. Theoretically, the runner-up in its original heat – call it S2-2 – may be faster than S3, so it is not eliminated yet either. But the other three horses in that heat already have the winner of the semifinal, S2 and S2-2 ahead of them. 3 more horses are eliminated.

The winner of the semifinal – S1 – is clearly the fastest horse of all. Moreover, the next two finishers in its original heat – S1-2 and S1-3 – still have not been compared with other contenders and remain in the pool. But the remaining 2 horses from that heat are obviously eliminated.

So, we now have just 6 horses – S1, S1-2, S1-3, S2, S2-2, S3 – as the remaining candidates. And because we know who the fastest is – S1 – we are only left with 5 horses to determine the second- and third- fastest.

Just one more run – #7 – and we are done.

I guess my mental abilities are not where I thought them to be anymore. Old age as an excuse?

I think that creating a tourney bracket on this problem would have been very helpful.

I see the solution much clearer now. At least I claim to have the initial correct approach.

<angrily shakes fist in the air>

Nice puzzle, Ilya. I can’t wait until that comes up in real life – I’ll be well prepared. 😉