17
$\begingroup$

This question discusses a well-known problem where you are given 25 horses and a five-lane track. You are asked to find the minimum number of races (maximum 5 horses per race) to determine the fastest 3 horses.

You have no stopwatch or other absolute method of measuring time. The only way to know if a horse is faster than another horse is if it finishes before the other horse in the same race.

If we slightly modify the original question to state that you need to know the relative speeds of all 25 horses (instead of just the top 3), what would be the minimum number of races required?

|improve this question
$\endgroup$
  • $\begingroup$ Just to clarify, I assume in this problem you have no objective way of measuring a horse's speed (like a clock or stopwatch), and can only make subjective determinations (like Horse A is faster than B)? $\endgroup$ – Patrick N Nov 26 '15 at 1:06
  • $\begingroup$ For reference, the question mentioned is this one. $\endgroup$ – f'' Nov 26 '15 at 2:00
  • 3
    $\begingroup$ $\frac{\log(25!)}{\log(5!)}\approx12.1$, so 13 is a lower bound on the answer. $\endgroup$ – f'' Nov 26 '15 at 2:01
  • 1
    $\begingroup$ An equivalent question has been asked on Math.SE here, with no answers. $\endgroup$ – f'' Nov 26 '15 at 2:04
  • $\begingroup$ I assume you are looking for the best worst-case performance? $\endgroup$ – frodoskywalker Nov 26 '15 at 7:40
8
$\begingroup$

Worst case 20 races, best case 13 races

Run all 25 horses in 5 races to get the following partial order, with each letter corresponding to a horse's completion time (which we assume for simplicity to be constant for each horse regardless of the number of races run).

a < b < c < d < e
f < g < h < i < j
k < l < m < n < o
p < q < r < s < t
u < v < w < x < y

Call these the initial 5 chains. The best of these are afkpu, whose relative order we don't yet know. We repeatedly race the fastest horses with unknown relative order against each other. Sometimes, fewer than 5 horses would be required, in which case we put in the next fastest of some of the chains.

Race 6 ('best of the best'): afkpu Assume without loss of generality that a < f < k < p < u . The fastest horse is then a. Remove a from the pool (of horses that must still compete) and continue.

Race 7 ('runners up'): bfcgk From the initial 5 chains and race 7, we know the next fastest horse is one of bf. The fastest horse after that would either be the other (of bf) or one of cgk; all other horses are slower than these 4. The winner and runner up of race 7 are awarded positions 2 and 3, and then removed from the pool.

Consider the initial 5 chains. In each chain, the remaining horses still form a single chain, so we still have 5 chains, though some will have fewer than 5 horses. Repeat the 'best of the best' and 'runners up' races to get 3 horses every two races (thanks @IvoBeckers). When there are at most 5 horses remaining in the pool, run them all in a single race to determine the bottom 5 positions.

Calculations: races 1-5 yield no positions, the first 21 positions are determined in the next 14 races, and the last race determines the final 4 positions. Total 5 + 14 + 1 = 20 races in the worst case.

Best case: use the above method, but assume the most convenient winning pattern possible to get more than 2 placings per race after race 6.

Race 6: afkpu, a=1.

Race 7: bfcgk, b=2,f=3,c=4. After bf are removed, the fastest 3 horses according to the established partial orders are cgk, all of which are in race 7, so we get 3 placings from this race. Assume g < k since we're looking for the best case.

Race 8: dgehk, d=5,g=6,e=7. We only really need dg for the 'best of the best', so we have room for 3 more - choose ehk. This race now also has the composition of a 'runners up' race, so we get 2 placings dg. In the best case, e also places, and all the remaining horses in the pool are slower than either h or k.

Race 9: hkilp, h=8,k=9,l=10. We don't need a 'best of the best' race since hkpu are already ordered, so this is just a 'runners up' race. In the best case, hk take out the next 2 placings, and we get a bonus placing since the remaining pool is slower than at least one of ilp.

Race 10: impjn, i=11,j=12,m=13. The 'best of the best' only needs to sort imp, so we have room for 2 more - choose jn. If ij are fastest in this race, the remaining pool is slower than at least one of mp.

Race 11: npoqu, n=14,p=15,o=16. The 'best of the best' only needs to sort np; add oqu. If np are fastest in this race, the remaining pool is slower than at least one of oqu.

Race 12: qurvs, q=17,r=18,u=19. The 'best of the best' race is not needed.

Race 13: svtwx, s=20,t=21,v=22,w=23,x=24,y=25. Last 6. Race all except one of the last in its chain (say, y). If the loser of race 13 (say x) is also in that chain, the chain places the remaining horse last (we already know x < y).

|improve this answer
$\endgroup$
  • $\begingroup$ If you race ejoty, then you determine last place, and you can determine second-last and third-last at the same time with one more race. Does that reduce the number of races by 1? $\endgroup$ – f'' Nov 27 '15 at 5:41
  • $\begingroup$ @f'' Thanks, though I don't think that helps since you get the last 5 positions all at once with the final race. $\endgroup$ – Lawrence Nov 27 '15 at 6:38
  • $\begingroup$ Isn't it that you can always get 3 positions for every 2 races? After the initial 5 races you need 2 races to get the top 3. If you remove those 3 from the set and take again a race with the top of every chain, do the same trick to get another top 3 (which will be position 4,5 and 6) and go on like that? $\endgroup$ – Ivo Beckers Nov 27 '15 at 14:27
  • $\begingroup$ @IvoBeckers I think that works - I'll add it to the answer. Thanks! $\endgroup$ – Lawrence Nov 28 '15 at 0:53
  • $\begingroup$ Yeah just ignore what i said, out of the country so just sporadically reading stuff on here, and yes, it wasnt specific to your strategy, so will remove the comment $\endgroup$ – DrunkWolf Dec 1 '15 at 15:02
4
$\begingroup$

Using a kind of binary search, where you have a few "constant" horses and you rank the rest of them as being faster or slower than your constants, would certainly get the job done.

Pick three horses at random (let's call them A, B, and C), and run them together in 11 races such that they match off against the 22 other horses, and therefore establish an absolute ranking for all three, recording which horses were better or worse than them in each race.

Best case: 16 races

A comes in (for example) 6th overall, B comes in 12th overall, and C comes in 18th (specific positions don't really matter, as long as they're separated by five horses). Race the 5 horses faster than A, and the 5 horses faster than B but slower than A, and the five faster than C but slower than B, and you've established a ranking of 18 of the horses in 14 races. Then, repeat with the remaining seven, keeping three of the horses constant, doing TWO (thanks, Dr Xorile) more races to rank the remainder (again, assuming best case. Ranking seven horses in this manner may require as many as three races).

Worst case: 48 races

If all three chosen horses place so that the rankings of the 22 remaining horses form a sequential list (i.e. A, B, and C come in 1st, 2nd, and 3rd or 1st, 24th, and 25th) that is the worst case, as it tells you nothing about the remaining horses and no meaningful partitions can be made. If this bad luck is repeated for the rest of the ranking, you will require 48 races to establish a rank for all 25 horses (assuming you naively continue using this strategy all the way through).

Average case: 22 races

I've calculated the average for all ${25 \choose 3} = 2,300$ possible choices of three horses to be 22. Which is actually much better than I was expecting for an average case. I found this by calculating the average races needed for 6 horses, then seven, then eight, etc. and then subbing those values in when there was a gap of that size between the rankings of two "constant" horses.

|improve this answer
$\endgroup$
  • $\begingroup$ It seems to me that (a) best case is 16 races (you can figure out 7 in two if you're lucky), (B) that worst case is a bit more (11+10+8+7+5+4+2+1) $\endgroup$ – Dr Xorile Nov 27 '15 at 1:40
  • $\begingroup$ I'm sad that I missed the seven in two races possibility. Thanks. But I'm pretty sure that set of terms you listed also adds up to 48 :P $\endgroup$ – Steve Eckert Nov 27 '15 at 4:55
  • $\begingroup$ How embarrassing. It looked larger in my head $\endgroup$ – Dr Xorile Nov 27 '15 at 5:32
  • $\begingroup$ Your given worst case is easily avoided: pick 5 horses at random for the first race, and call the winner A, the 3rd place finisher B, and the loser C. $\endgroup$ – Peter Taylor Dec 3 '15 at 20:35
-4
$\begingroup$

answer is 7 races

Solution

Step 1: First, we group the horses into groups of 5 and race each group in the race course. This gives us 5 races.

W11 W12 W13 W14 W15

W21 W22 W23 W24 W25

W31 W32 W33 W34 W35

W41 W42 W43 W44 W45

W51 W52 W53 W54 W55

Step 2: we race the 5 level 1 winners(w11,w21,w31,w41,w51) ans assume winning order of this race is w11,w21,w31,w41,w51

Step 3: BECAUSE WE NEED TOP 3 AND W41 HAS COME 4TH Position that is the reason we don't need to consider W41 W42 W43 W44 W45 and also W51 W52 W53 W54 W55

now we have

W11 W12 W13 W14 W15

W21 W22 W23 W24 W25 W31 W32 W33 W34 W35

Step 4: because we need top 3 then dont need W14 W15 W24 W25 W34 W35 now we have

W11 W12 W13

W21 W22 W23

W31 W32 W33

Step 5: because in 6th race W31 has come on 3rd position that is the reason we do not need to consider W32,W33 and also we will not consider W23 now we have

W11 W12 W13

W21 W22

W31

Step 6: top 1 is already achieved which is W11(winner of 6th race) remaining are

W12 W13

W21 W22

W31

Step 7: now race W12 w13 w21 w22 w31 to get 2nd and 3rd winner

Hence answer is 7 races.

Another variation which is asked in google interview

  1. 25 Horses 5 Tracks 5 Fastest Horses Puzzle ➤ (http://codinginterviewquestionsans.blogspot.in/2017/07/25-horses-5-tracks-5-fastest-horses.html)
|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Question is asking for which horses are 4th fastest to slowest as well. Your answer does not provide a method to determine relative speeds of those 22 horses. Downvoted. $\endgroup$ – Hakdo Jul 19 '17 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.