Friday, 18 August 2017

Find fastest 3 horses out of 25 horses puzzle

Question

You have 25 horses and you need to pick fastest 3 horses out of those. In each race you can race maximum of 5 horses as there are 5 tracks available. What are minimum number of races needed to find the fastest 3 without using a stopwatch.

7 races needed.

Understanding

Since we don't have a stopwatch only way to find fastest is by racing horses. Lets have 5 races each of 5 horses and let following be the results -

• 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
Above are results of each race.  We have 5 races till now. Now lest race between fastest of all previos 5 races i.e A,F,K,P,U. We have 6 races till now .Let's say the result for that is -
• F > K > A > P > U

Since We are interested in top 3 P and U are useless for us. Also since P and U were fastest among their group we can ignore all members of P and U too. So now only horses under consideration are -

• F > G > H > I > J
• K > L > M > N > O
• A > B > C > D > E
Now if we consider A as possible candidate for top 3 then others in group of A are redundant - since we already have F and K faster than A. So we can ignore B,C,D,E

Now horses under consideration are  -

• F > G > H > I > J
• K > L > M > N > O
• A
Now in the group lead by k possible horse candidates are K and L - since F is already faster than K if we consider K and L we already have 3. So we can ignore M,N and O. So remaining horses are -

• F > G > H > I > J
• K > L
• A
Now lets consider group led by F. We can consider G and H as possible candidates for top 3 since if they are I and J are redundant. So remaining now are -

• F > G > H
• K > L
• A
Now we already know fastest among all in F since we got that result by running fastest among each group. So only horses we need comparison for 2nd and 3rd position are - G, H, K, L, A

These are 5 horses we can have another race and find the top 2 out of them. Lets say the result was -
• L > H > K > G > A
We have done 7 races now. So fastest onces are L and H. We already the fastest among all - F. So the final answer is -
• F > L > H
So the answer is 7 races needed.