July 26, 2008

Horse Problem

There are 25 horses and 5 race tracks.
We have to pick the fastest three horses in the
least no of races. PS: In one race only 5 horses
can participate. Find the least number of races?

Anonymous said...

6 races

first pehle 25 horses 5 tracks me dodaye jaynege aur unmese jo pehle aayenga ushe last track 6 me dodayenga right aur ushe race me first three milenge...

satish said...

6

Varun Rao said...

Only 5 races are enough. Time will tell you.

not always right

suppose in the first race, you get the top runners overall. Unlikely, but possible. With only 6 races, you you definitely get the top ONE, but not the top THREE.

but i don't know the answer :-(

Mohit said...

11

Anmsoft said...

Pick 5 Horses for race, after race replace the slowest with new 1 from the remaining 20. Perform the race again, replace the slowest with new 1 from the remaining 19 and so one continue until all of them get a chance i.e total 21 races to decided the top 5 fastest.
21 = 1 race for 5 + 20 with 1 replacement each.

anuj said...

The problem is like external merge sort. so following the above procedure, 11 races are required to get 3 fastest horses...

Mustafa said...

8 races.

In First 5 races, we number the horses according to their position.
1 2 3 4 5 - R1 (Race 1)
1 2 3 4 5 - R2 (Race 2)
1 2 3 4 5 - R3 (Race 3)
1 2 3 4 5 - R4 (Race 4)
1 2 3 4 5 - R5 (Race 5)

In Next race we take topmost horse from each previous races, to get fastest horse. But we will also mark 2nd and 3rd position of horses in the 6th race.

Let us suppose the result is
R1 - first
R4 - second
R5 - Third

We can safely remove all horses of R2 and R3. Because if their top most horse is not able to finish in top 3, there is no chance that there other horses will be in top 3.

Now in next race there will be only 3 horses.

Second horse from R1
Top horse from R4
Top horse from R5

After this race we will get second topmost horse. (Race no 7)
If top most horse in this race is Second horse from R1 then next race will be in between

Third horse from R1
Top horse from R4
Top horse from R5

If top most horse in this race is Top horse from R4( Similarly for R5) then next race will be in between

Second horse from R1
Second horse from R4
Top horse from R5

After this race( Race 8 ) we will get the Third topmost horse.

You can also take some other combinations also in the above, but for all combinations the answer will be 8 races.Correct me If I am wrong.

Ajay said...

detailed explanation is given in that blog...

Anonymous said...

if you have timers and a sheet of paper, the answer is 5. Record the times taken by each horse and find the top 3.

Otherwise,

Run set of 5 horses and pick the top 3 in each lot.
So now we got 15 horses to compare.
Repeat the step, and we will narrow down to 9 horses.
Repeat again and we will narrow down to 6 horses.
Repeat it with first 5, and run the left alone horse with the third place horse in the first lot.
Now we got our top 3.
Number of steps: 5(25horses) + 3(15horses) + 2(9 horses) + 2(6 horses) = 12 races.

Anonymous said...

7 races...

5+1+1=7
five races for top three in each group

sixth race for fastest

seventh race for second n third

Anonymous said...

7 races....