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