Saturday, March 24, 2012

Given N horses, how many races do you need?

Given N horses, how many races do you need to identify top 3 horses. Assume that a race cannot have more than 5 horse together.

1 comment:

  1. Looks like the post is duplicated.

    Arrange the horses into 5 groups, and race each group. We have 5 ordered sets. Again race the winners of each group. Now we can arrange the horses as two dimensional array in which each row (group) is sorted and first column (winners of each group) is also sorted as per outcome of 6th race.

    By virtue of observation, the horses in last two columns and last two rows can't be in first 3.

    We are left with 9 horses, of which winner is the best horse. Out of the remaining 8 horses, we need to trace 2nd best and 3rd best.

    Again by virtue of observation, 3rd horse in second row and 2nd, 3rd horses in third row can't participate in best 2nd or best 3rd place.

    Finally we left with 5 horses. Race again to find 2nd best and 3rd best.