And the winner takes it all!

Logic Level 2

There are 25 horses and a 5 lane race track. We want to find the TOP 3 horses among them. But we are in the yesteryear with no stopwatch and no digital machines to count the time to milliseconds. So we can only reply on the photo finish to compare across the 5 horses in one race, but cannot compare the results across different races. However, we know that each horse takes EXACTLY the same time to finish the race, no matter how many times we make him run.

What are the minimum number of races we need to conduct in order to find the TOP 3?

9 7 10 6

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Richard Desper
Oct 27, 2020

First, separate the horses into five groups of five. Run a heat for each group of five. Let's identify the heats as A,B,C,D, and E, and identify each horse by heat and finishing order. For example, C4 is the fourth horse in heat C. We can immediately dismiss from consideration any horse that isn't in the top 3 of its heat.

Now run a heat with all the first-place finishers of the five previous heats: A1, B1, C1, D1, and E1. The winner of this heat is the fastest horse.

Without loss of generality, A1 wins this heat, B1 finishes second, and C1 finishes third. D1 and E1 are now eliminated (as are all the other horses from the D and E heats.)

The only horses that could be second fastest are A2 and B1. The horses that could be third fastest include A2, A3, B1, B2, and C1. Note that C2 is slower than C1, which is slower than two other horses, while B3 is slower than B2, B1, and A1.

Run a heat with these five horses: A2, A3, B1, B2, C1. The winner is the second-fastest horse and the 2nd place finisher is the third fastest horse.

Rupen Kohli
Dec 27, 2017

The critical information given to us is that each horse takes exactly the same time to finish the race, no matter how many times he runs.

Now to start off, we make the 5 necessary runs, by randomly making 5 batches of 5 horses, and find the top 3 in each race by our naked eye/ photo finish. The ranking chart would look something like this. H-(Ra)b denotes that horse ran in the Number 'a' lineup and got position 'b'.

H-(R1)1 H-(R2)1 H-(R3)1 H-(R4)1 H-(R5)1 H-(R1)2 H-(R2)2 H-(R3)2 H-(R4)2 H-(R5)2 H-(R1)3 H-(R2)3 H-(R3)3 H-(R4)3 H-(R5)3 H-(R1)4 H-(R2)4 H-(R3)4 H-(R4)4 H-(R5)4 H-(R2)5 H-(R2)5 H-(R3)5 H-(R4)5 H-(R5)5

For our next race, we line up the top 5 horses from each race, viz. {H-(R1)1 H-(R2)1 H-(R3)1 H-(R4)1 H-(R5)1} The winner of this race is definitely the Number 1 horse among all the 25. We will also obtain the number 2 and Number 3 in this race.

Let us assume that top three horses in this 6th race are H-(R2)1, H-(R5)1 and H-(R1)1 respectively. Then, after the Number 1 spot, possible horses who can take the Number 2 spot are either the second horse in this 6th race, or the second horse in the preliminary race in which Number 1 horse ran. That is, it can be either H-(R5)1 or H-(R2)2. We cannot ascertain right now because there is no way to compare among them directly. Similarly, overall Number 3 spot can be taken by either the Number 3 horse in the sixth race, or the second ranked horse in the race in which the Number 2 horse of race 6 ran, or the third ranked horse in the race in which the Number 1 horse ran. That is, it can be either H-(R1)1, or H-(R5)2, or H-(R2)3.

So for the overall Number 2 and Number 3 positions, we have possible 5 horses. The above analysis could be done for any random ranking in the 6th race, and we shall still get the same number of horses competing for these spots. Hence, we shall now conduct the 7th race of these 5 horses. The winner among them will be the overall Number 2 horse, and the runner up will be the overall Number 3 horse.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...