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!!

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

ReplyDeletenope sandy... the answer is not 12

ReplyDelete8 races is that right ?

ReplyDeletemake 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

is it 8?

ReplyDelete@rushabh...

ReplyDeletenope...

answer is not 8...

Its 7... good attempt though...

make 5 groups and then it and race each group once

ReplyDelete6th 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

yeah the answer is 7 races

ReplyDeleteThere 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

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

ReplyDeletekya faart hai

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

ReplyDeletegood angush...

ReplyDeletecorrect solution...

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

yo mishra...

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

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

anyways, treat to Mishra :P

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

ReplyDelete:)

ReplyDeleteForm 5 groups to find 5 winning horses, run them for 6th race

ReplyDeleteAfter 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)

@gyani.. good explanation...

ReplyDeletethanx...

too late though :P

I didnt solve it

ReplyDeletebut once you know that the answer is 7

u get how to do it :P

:)

ReplyDeletePandeyji ka swagat hai!! :)

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

ReplyDelete:)

ReplyDeleteGuys!! 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..

:)