Thursday, October 13, 2011

Horse Race

Question:
Given 25 horses and 5 horses in a race, find the minimum number of races needed to find top 3 horses.

Answer:
7
Step 1: divide 25 horses into 5 groups, each group a race;
Step 2: pick the horses in 3rd place from each group above, then race and suppose get A > B > C > D > E (here '>' means faster);
Step 3: pick the first 3 horses from the group containing A and first 2 horses from group containing B, run a final race.

Below is an illustration.

No comments:

Post a Comment