25 horses puzzle - find minimum number of races.

Questions....

Given 25 Horses, each of them runs at different speeds.
one can race max 5 horses at a time.
there is no way to calculate the timings.
What is the minimum number of races needed to find out fastest 3 horses.


Answer.....


1. Divide 25 horses into 5 groups of 5 horses each. Race all groups. we will get 3 fastest from each of the groups.

2. now race fastest 5 horses from each race. this will give 1 fastest horse from all horses. elimiate the last two horses.

3. take 2nd and 3rd horse from last race, 2 and 3 from last from the group to which fastes horse belongs( it may possible that 3 fastes horses may be from same group). take the 2nd fasted horse from the group two which 2nd fastest horse belogs from race in last step.

4. do the race for horses selected in step 3, this will give 2nd and 3rd fastes horse.


IT will take minimum 7 races to find fastest 3 horses.

1 comment:

Joe said...

the answer is definitely 7, read here for detailed explanation:

http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/

Your Title

My Blog List