Brain teasers from Work

[quem98]

1. There are 25 horses. Each horse runs at a unique constant speed. You would like to determine which are the three fastest horses. You are allowed to race 5 at a time. You cannot time the races; you can only observe relative order of finish. What is the minimum number of races necessary to identify the top 3 with certainty? How

Comments

[oldsilenus]

Out of those posted so far, yours is the only answer to the first question which is correct.

I've come up with a different correct way to do it, and, oddly enough, it also takes eleven rounds.

First round - five races: Race each horse once, in a group of five. So, horses 1-5 in one group, then horses 6-10, then 11-15, then 16-20, then 21-25. Eliminate the fourth and fifth place horses from each group. You now have 15 horses left.

Second round - three races: Race each horse once, in a group of five. As there are 15 horses left, this will take three rounds. Eliminate the fourth and fifth place horses from each group. You now have nine horses left.

Third round - three races: Race one: Race the first five of the nine horses left. Eliminate the fourth and fifth place horses. Race two: Race the first, second, and third place horses from the previous race along with two more of the remaining horses (of which there are currently four). Eliminate the fourth and fifth place horses. Race three: Race the first, second, and third place horses from the previous race along with the remaining two horses. The firth, second, and third place horses in this race are the first, second, and third fastest horses from this group of 25 horses, respectively.

[spwebdesign]

I reached the same conclusion, but my third round differed from yours. No need to punish the top 3 horses by making them race more! Instead, in the third round, race horses 1-5, and then 6-9 plus the third place finisher of the 1-5 race. It's conceivable you may not need the 11th race, for if the third place finisher of race 9 finishes race 10 second or higher, you know which the top 3 horses are with certainty.