Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Oct 5, 2009

Top 3 out of 25 horses

Problem posed to me by Ankit Goyal (Civil, H2)

There are 25 horses. You want to find the best 3. Of course having a race and finding the top 3 is easy, but the constraint is that only 5 horses are allowed to race at once. Find the top 3 horses having minimum number of races.

Solution:

Post your answer here. The first to reply with a correct answer (except Ankit) gets an H8 canteen treat!!!

Update (11/12/09): Solution by angush (Ankur Mishra, H7, IITB) in comments!!

19 comments:

  1. the answer is 12 races.... is it right??

    ReplyDelete
  2. nope sandy... the answer is not 12

    ReplyDelete
  3. 8 races is that right ?
    make 5 groups and then it and race each group once
    then race the top rankers to know position1
    then eleminate him from that group so we are left with 4 grps of 5 horses and 1 grp of 4 horses in sequenced order
    repeat the procedure to know 1 2 and 3 so
    for n th position no of races = 5 + n

    ReplyDelete
  4. @rushabh...

    nope...
    answer is not 8...

    Its 7... good attempt though...

    ReplyDelete
  5. make 5 groups and then it and race each group once
    6th race-then race the top rankers to know position 1,2,3
    now position 1 is final position 1.
    7th race- pick 2nd & 3rd horses from the group to which the position 1 belongs & pick 2nd from the group to which the 2nd horse of 6th race belongs & the horse that came 3rd in 6th race..from this race u get the final 2nd & 3rd position

    ReplyDelete
  6. yeah the answer is 7 races

    There are five group of initial horses (A,B,C,D,E) name the horses as A1,A2,A3,A4,A5... according to their groups and their position in the initial 5 intra group races

    Now we are left with A1,A2,A3,B1,B2,B3,C1,C2,C3,...E1,E2,E3
    i.e 15 horses.

    6th race is between A1,B1,C1,D1,E1
    this gives us the 1st position horse

    Suppose the winner is B1, second comes D1 and third E1 implies A1,C1 are out, implies A and C groups are out. This also implies E2 & E3 are out, D3 is out since D1 may be second (from 6th race) so D3 is definitely out

    Now confusion is between B2,B3,D1,D2,E1....second and third overall are the first and second two of this final race which is the 7th race

    Answer solved by hussain and sandy

    ReplyDelete
  7. kya faart hai humne pehle kiya hai solve type karne mein late ho gaya
    kya faart hai

    ReplyDelete
  8. I m ankur mishra...H7 ... bhool gaya

    ReplyDelete
  9. good angush...
    correct solution...

    @hussain,sandy.. missed by a few seconds.. good neways :)

    ReplyDelete
  10. yo mishra...

    koi na hussi... agli baar kar dena.. :)

    BTW, mishra se pehle rushabh ne mujhe aa ke solution dikha diya tha :)

    anyways, treat to Mishra :P

    ReplyDelete
  11. mere badle sandy aur hussy ko tr8 dedo...me baad me unse treat lelunga :)

    ReplyDelete
  12. Form 5 groups to find 5 winning horses, run them for 6th race
    After 6th race, standings are:

    1-1, 1-2, 1-3, 1-4, 1-5
    2a, 2b, 2c, 2d, 2e
    3a, 3, 3, 3, 3
    4, 4, 4, 4, 4
    5, 5, 5, 5, 5

    Conduct 7th race among (1-2, 1-3, 2a, 2b, 3a)

    Short Logic- Sets 1-4 and 1-5 get discarded completely (after 6th race)and lower 4, 3, 2 positions of Set c,b and a (As they can in no way be among in top 3)

    ReplyDelete
  13. @gyani.. good explanation...

    thanx...
    too late though :P

    ReplyDelete
  14. I didnt solve it
    but once you know that the answer is 7
    u get how to do it :P

    ReplyDelete
  15. CLR kaa question lag raha hai... median in O(n) wale chapter se

    ReplyDelete
  16. :)

    Guys!! Sorry to be CS type here :)

    @parakram
    CLR had an algorithm to find the median in O(n). Although the diagram formed is similar (set of fives) and elimination is similar (by transitive rule), the problems are not even related. Note that this idea would even work when the problem says 6 horses at a time. CLR case worked only for 5. :)

    Interesting you saw a relation between the solutions of the two problems... Thanx..
    :)

    ReplyDelete