Nov 8, 2009

25 horses problem



You have 25 horses, what is the minimum number of races you need to find the top 3 (in terms of speed)? In one race you can race 5 horses, and you don't have a timer.


Assume that horses never get tired and they may be raced any number of times without having their speed affected.

4 comments:

  1. divide in group of 5 ... 5 races...
    neglect all the last two horses in races...15 left
    take the top 5 of all 5 races...1 race...
    position 4 and 5 in that race out(also rest 2 of that group out too)..9 left...
    final race...group 1 (from where the horse came first in 6th race)..2 horses....group 2 (top horse came second in 6th race...)..1 horse..last in that group is neglected as it came third to second position horse...group 3...only the top horse..rest are neglected as they came lower thn the third position horse in 6th race...

    6 horses left..one is at top already..rest five compete...top two will be second and third

    ReplyDelete
  2. 1. Divide in groups of 5 - A,B,C,D and E
    2. Choose Winner from 5 races hence No. of races till now will be = 5
    3. From Step 2 , Race these and choose top 3. =6
    4. Lets say A1,B1 and C1 won the race from respective groups.
    5. Race the B1 with A's Group. If A's group looses = 7
    then Go to Step 6 else go to STEP
    6. Race the C1 with A's and then Winner will be in 3rd Position = 8

    7. Select the winner from 5 and if C1 is 2nd then Order is decided else Order will be A1,A2,A3. = 8

    Hence minimum number of Steps Required = 8

    ReplyDelete