• RSS
  • Facebook
  • Twitter

Knowledge is Power.

  • Who you are ?

    Working on machines without understanding them ? Then you should be here..

  • Where you are ?

    Geographical location should not become a barrier to Share our knowledge.

  • What do you do ?

    Puzzles and Interview question are intended to be discussed here.

    Thursday, February 25, 2010

    You have 25 horses. You have 5 tracks to race on. We need to find 3 fastest horses. How many minimum races required to find that ? We have no stop-watch. Horses run at same speed.

    Now this puzzle is deceptive if you are not careful enough.

    Solution :

    Divide the set of 25 horses into 5 non-overlapping sets of 5 horses each.
    Have a race each for all the horses in eachset.
    This makes it a total of 5 races, one for each set.

    Now, have a race for the winners of each of the previous 5 races.
    This makes it a total of 6 races.
    But this step is tricky. We need to use the following logic
    to identify horses for this race.

    Observe the position of each horse in the 6th race and correspondingly
    number the sets. i.e. the set of the winner of 6th race will be said to be set no. 1
    while the set of the loser of the 6th race will be said to be set no. 5.

    Now, possible candidates for the first three positions :
    1. No horse from set 4 or set 5.
    2. No horse from set 3, except for 1st Rank from this group.
    3. No horse from set 2, except for 1st and 2nd Rank from this group
    4. No horse from set 1, except for 1st, 2nd and 3rd Rank from this group

    So now we have 6 candidates for top 3 positions. However, we know that the winner
    of set 1 is the fastest horse in the whole group of 25 sets.

    So now we have 5 candidates for the second and third position.
    What better way to find out who’s who than to have a race of these 5 horses. Race them and this will solve our
    problem in just 7 races.

    0 comments:

    Post a Comment