An Algorithm Challenge (finding the five fastest horses out of a large group)

[Hornbein]

As a Bedouin schiek you own twenty-five horses. You want to find the three fastest. You have no clock or other device that measures time. Your racing field is wide enough that five horses can race unimpeded, so you can race five at a time and see how they place. You don't want to abuse your mounts or jockeys so...how to schedule the minimum number of races that will give you what you want to know?

I couldn't do it but a day later the answer popped into my head.

 

[Ibix]

I can do it in seven races.

Spoiler: Here's how it sheiks out

Round 1: Split your horses into five fives and run five races.

Round 2: Race the winners of each race from round 1. Label the horses A-E in order of best to worst times.

A, B and C are possibles but D and E are out and, since D and E were the fastest in their round one races, so are all the other horses in their races.

C is currently our slowest candidate, and is known to be faster than all other horses in its round 1 race, so they're out too.

B is our second-slowest candidate, so #2 in its round 1 race could be faster than C. All others are out because, although they could be faster than C (not $c$), they are not faster than A, B, or the #2 in B's race and hence cannot be in the top three.

A is the fastest of the fastest, so is definitely in. #2 and #3 in its race could be faster than B or C. All others are out, because even if they're faster than B or C we know they're slower than A, A's #2 and A's #3.

So we have five horses remaining in consideration: B, C, A's #2 and #3, and B's #2. These are all slower than A and faster than the eliminated horses, but we don't know the complete order among them.

Round 3: Race those five. Keep the top two, along with A.

Five races in round 1 plus one each in rounds 2 and 3 is a total of seven.

...assuming, of course, that we have spherical horses travelling in a vacuum so they always run at the same speed - otherwise there isn't a well defined ordering.

 

[PeroK]

Here's another question. You have a number of items that are all same weight, except one which is lighter than the others. You have a set of scales that can hold any number of items in each side. See image.

What is the optimum strategy for identifying the odd item out?

E.g. suppose there are 96 items. How many times do you need to use the scales?

 

[Baluncore]

Log₃(n)

 

[hutchphd]

...assuming, of course, that we have spherical horses travelling in a vacuum so they always run at the same speed - otherwise there isn't a well defined ordering.

Are those the fabled Aroundian breed?

 

[Vanadium 50]

I can do it in seven races.

As can I.

The strategy adopted by the OP is "wait for a flash of insight". A fine strategy, one I have used myself on many occasions. But can we give a little more shape to the problem?

The answer must be at least 6. Fewer than 5 and you havem't run all the horses. Five races gives you no comparison between horses in different races, so it must be at least 6.

On the other extreme, I could run every horse against every other jorse (two pairs at a time to use 4 of the 5 lanes) and you need 25 (horses) x 24 (horses - 1) / 2 (order doesn't matter) / 2 (2 sets of 4 lanes) oe 150. So now the answer is bounded between 6 and 150.

Now see where the "obvious" algorithm falls. Run a race, keeping the top 3. Add two horses from the 22 that have not bveen run, and run another race of 5. Keep the top 3 and kep going. You have your answer after 12 races. So the answer needs to be between 6 and 12.

By this point, you know the answer is one of 7 numbers, and hopefully have gained enough insight to see the problem: on average the fastest horse is raced 6 times. You are also gaining information on the relative rankings of the slow horses.

If only there were a way to quickly identify the very fastest and very slow horses and remove them from further consideration....

 

[Mark44]

You have a number of items that are all same weight, except one which is lighter than the others.

How can the items all be the same weight, but one of them is lighter. Sounds like they are exactly the same, except different.

 

[DaveC426913]

How can the items all be the same weight, but one of them is lighter. Sounds like they are exactly the same, except different.

Hey now "all except one" is a valid, well-defined value.
n-1

 

[PeroK]

Log₃(n)

If $n =4$, then we can definitely find the item in $2$ measurements and possibly in $1$ measurement. If we have a strategy of putting one item on each side of the balance, then we get $1$ or $2$ with equal probability. We have possible answers for $n = 4$ of $2$ (maximum) or $1.5$ (average).

Whereas, $\log_3(4) \approx 1.26$. That's not the answer. Although $\log_3(n)$ rounded up to the nearest integer should give the maximum number of measurements.

 

[Baluncore]

That's not the answer.

Correct. It was a hint, not a full answer.

Log₃(96) ≈ 4.154 ; So a maximum of 5 comparisons.
That is because the partial 0.154 comparison, will still require a comparison of something.

 

[Hornbein]

Log₃(n)

Huh. That hint made it too easy.

 

[Mark44]

You have a number of items that are all same weight, except one which is lighter than the others.

How can the items all be the same weight, but one of them is lighter.

Hey now "all except one" is a valid, well-defined value.

Right, but the statement in the first quote says that there "a number of items that are all the same weight..." followed by "except one"

A clearer and precise way of writing this is "in a collection of items, all but one are the same weight, and the remaining one is lighter." See, that wasn't so hard.

 

[Mark44]

@PeroK, I see that you have responded twice to my posts with a Sad emoji. Do you not understand that what you wrote is at best unclear? Or that there is a difference between what you wrote and saying "all but one are the same weight, and the remaining one is lighter"?

 

[PeroK]

@PeroK, I see that you have responded twice to my posts with a Sad emoji. Do you not understand that what you wrote is at best unclear? Or that there is a difference between what you wrote and saying "all but one are the same weight, and the remaining one is lighter"?

You're wrong. My usage is correct, standard English.

https://www.macmillandictionary.com/dictionary/british/except_1

One example given by MacMillan is:

She was dressed all in black except for a white lace collar.

 

[Mark44]

My usage is standard English.

Maybe so, but it sounds clumsy to my ear.

You have a number of items that are all the same weight, except one whichthat is lighter than the others.

I like this better: All but one of the items are the same weight, and the remaining one is lighter.

 

[PeroK]

Back to the problem. I found one anomaly to the rule that the sequence increases with increasing $n$.

For n = 6, the best average is 2. If you measure 2 on each side, then you always take two measurements. And, if you measure 1 on each side first, you still get an average of two measurements. Also if you measure 3 on each side.

For n = 7, however, if you measure 3 on each side you get the answer in two measurements six times out of seven and in one measurement one time in seven, giving an average of 13/7 measurements.

This means that the best approach for n = 18 is not to measure 6 against 6 first. Seven against seven is better. And, in fact five against five is equally good.

And, in fact, 13 and 21 are anomalies as well. You can do 13 faster than 12 and 22 faster than 21 (on average).

The general optimum strategy is not simple, apparently.

 

[pinball1970]

Here's another question. You have a number of items that are all same weight, except one which is lighter than the others. You have a set of scales that can hold any number of items in each side. See image.

What is the optimum strategy for identifying the odd item out?

E.g. suppose there are 96 items. How many times do you need to use the scales?

View attachment 327979

I would weigh half against half then split the lighter one each time. When I get to the last 3 I pinch one from the previous non light. Then it's 2 v 2 then 1v1. 6?

 

[PeroK]

I would weigh half against half then split the lighter one each time. When I get to the last 3 I pinch one from the previous non light. Then it's 2 v 2 then 1v1. 6?

You can do better that that.

 

[Ibix]

Last 3 just one v one. They are even it's the other, or one is lighter.
48, 24,12,6,3 then last makes 5.

A balance can read three things: left heavier, right heavier, or both sides the same. Your methodology only ever produces two of the possible outputs, so you are wasting opportunities to gain more information at every step.

 

[pinball1970]

Ok. Have to dash but I will come back to this

 

[Baluncore]

Ok. Have to dash but I will come back to this

The binary solution is the obvious choice, but is not optimum.
It is well worth the return.

 

[pinball1970]

The binary solution is the obvious choice, but is not optimum.
It is well worth the return.

Ok thanks for waiting and no spoilers. Just finished a four rehearsal and I was thinking of this all the way through!

 

[DaveC426913]

Maybe so, but it sounds clumsy to my ear.

Ah, but "clumsy" is a far cry from wrong (not that you actually said it).
Wrong would be worth a point-of-order; clumsy, not so much.
OK, moving on...

 

[PeroK]

Ah, but "clumsy" is a far cry from wrong (not that you actually said it).
Wrong would be worth a point-of-order; clumsy, not so much.

It's not even clumsy. For example:

All prime numbers are odd except $2$.

The modulus function is differentiable everywhere except $x = 0$.

That's just standard English usage, IMO.

 

[Baluncore]

All prime numbers are odd except 2.

Which must make 2 the oddest prime of all.

That's just standard English usage.

 

[Mark44]

Ah, but "clumsy" is a far cry from wrong (not that you actually said it).

The relevant part here is that I didn't actually say it.

All prime numbers are odd except 2.

The modulus function is differentiable everywhere except x=0.

These are reasonable examples of usage in that the "except" part isn't a separate clause that negates the universal clause. However, the first could be improved like so: "All prime numbers except 2 are odd.

Consider these, though:

All mammals are viviparous, except some aren't. (E.g., the platypus lays eggs.)
All integers are even, except some aren't.
A Ford Model T buyer can have the car in any color, except it must be black. (Paraphrase of a comment by Henry Ford.)

The conjunction "except" negates the preceding clause, so non-clumsy usage would move the "except" part inside the initial clause.

This is similar to statements that include "only" in the wrong place, such as the following:
"I only went fishing with Bill." Is the intent that the sole activity was fishing or was it that the sole companion was Bill? IOW, is it "only fishing" or "only Bill"?

 

[Vanadium 50]

Which must make 2 the oddest prime of all.

Six is odd too. A horse has two legs in back and forelegs in the front, and 2+4=6 legs in total, which is certainly an odd number of legs for a horse.

And four - the Oracle at Delphi warned Croesus about attacking Persia, and forewarned is forearmed. Which is certainly an odd number of arms for a man.

Now, can we split this digression off and move it where it belongs?

 

[pinball1970]

I cannot do the horses.
For the scales question.
Ok, Splitting into 3 lots of 32 I can get to a lower number quicker?
Instead of 48, 24, 12, 6,3. I get 3x 32 and I can dismiss 64 items straight away.
Then a 2x10 and a 12 let's assume it's in the 12.
Then I have 3x 4 then I have just 4.
Three moves to 4 quicker but..

 

[Ibix]

That's it for the scales, yes.

With the horses you should be able to find the fastest easily enough. At the point you know which one is the fastest, think about which horses could possibly be second fastest.

 

[PeroK]

I cannot do the horses.
For the scales question.
Ok, Splitting into 3 lots of 32 I can get to a lower number quicker?
Instead of 48, 24, 12, 6,3. I get 3x 32 and I can dismiss 64 items straight away.
Then a 2x10 and a 12 let's assume it's in the 12.
Then I have 3x 4 then I have just 4.
Three moves to 4 quicker but..

That's the idea. You can reduce the number by (approx) a factor of 3 each time.

It's then a question of what criteria you use to assess your strategy. The maximum number of measurements can be calculated using powers of three (or the inverse process: log to the base $3$).

If, instead, we look at the expected (average) number of measurements, then it gets suprisingly tricky. The example I gave above is that for $18$ items, you can do better than measuring $6$ against $6$. That's because you can find one light item from $7$ statistically faster than one light item from $6$. To be honest, I didn't spot that until I wrote a Python script to check all the possibilities!