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. We need seven races to find best 3 horses. Think of the horses in a two dimensional array. After first five races, we will have all the rows sorted. One more race among first column horses, will sort the first column, and relative rows. I mean, if the winner of this column race is from 3rd row, all the elements of first row and third row will be exchanged.

    After, 6 races we have first row first horse as top best one. We can eliminate last two rows and last two columns. By virtue of comparison, we will have five more horses to trace second best and third best.

    It is interesting to know how can we trace the 4th best, 5th best, so on...

    I found it would be useful to reduce the problem into Young Tableau where each row and each column is sorted. Using Young Tableau, we can find k-th best using heap data structure.

    Any other better approaches?