### 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:

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

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

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

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

4. @rushabh...

nope...

Its 7... good attempt though...

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

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

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

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

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

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

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

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

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)

13. @gyani.. good explanation...

thanx...
too late though :P

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

15. :)
Pandeyji ka swagat hai!! :)

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

17. :)

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..
:)