Question and Answers Forum

All Questions      Topic List

Permutation and Combination Questions

Previous in All Question      Next in All Question      

Previous in Permutation and Combination      Next in Permutation and Combination      

Question Number 3274 by Yozzi last updated on 09/Dec/15

I have 25 horses and I′d like to know which are the three fastest horses among them. I do not have a clock but I have a race track which can be used by 5 horses at a time. If each horse covers the distance of the track in the same time for every race it runs, find the least number of races that ought to be held in order to identify the three fastest horses.

$${I}\:{have}\:\mathrm{25}\:{horses}\:{and}\:{I}'{d}\:{like}\:{to} \\ $$$${know}\:{which}\:{are}\:{the}\:{three}\:{fastest} \\ $$$${horses}\:{among}\:{them}.\:{I}\:{do}\:{not}\:{have}\:{a} \\ $$$${clock}\:{but}\:{I}\:{have}\:{a}\:{race}\:{track}\:{which} \\ $$$${can}\:{be}\:{used}\:{by}\:\mathrm{5}\:{horses}\:{at}\:{a}\:{time}. \\ $$$${If}\:{each}\:{horse}\:{covers}\:{the}\:{distance} \\ $$$${of}\:{the}\:{track}\:{in}\:{the}\:{same}\:{time}\:{for} \\ $$$${every}\:{race}\:{it}\:{runs},\:{find}\:{the}\:{least} \\ $$$${number}\:{of}\:{races}\:{that}\:{ought}\:{to}\:{be} \\ $$$${held}\:{in}\:{order}\:{to}\:{identify}\:{the}\:{three} \\ $$$${fastest}\:{horses}.\: \\ $$$$ \\ $$

Answered by prakash jain last updated on 09/Dec/15

First 5 races with numbered results 1: h_1 h_2 h_3 h_4 h_5 2: h_6 h_7 h_8 h_9 h_(10) 3: h_(11) h_(12) h_(13) h_(14) h_(15) 4: h_(16) h_(17) h_(18) h_(19) h_(20) 5: h_(21) h_(22) h_(22) h_(24) h_(25) 2 elimnated from each group since they cannot take position 1 2 3 overall. 6th Race with toppers (h_1 , h_6 , h_(11) , h_(16) , h_(21) ) Let us assume results are h_1 h_6 h_(16) h_(21) h_(11) h_(11) /h_(21) is 4/5 among toppers all participants of race 3 and 5 are eliminated as they are slower than at least 4^(th) position Leave selection process limited to h_1 h_6 h_(16) h_2 h_3 h_7 h_8 h_(17) h_(18) h_(16) is at best 3^(rd) so h_(17) and h_(18) eliminated. h_1 h_6 h_(16) h_2 h_3 h_7 h_8 h_6 is at best second so h_8 can be at best 4^(th) . h_1 h_6 h_(16) h_2 h_3 h_7 Leaves 6. h_1 is first so it is clearly the first. need to find best 2 from remainin 5 h_6 h_(16) h_2 h_3 h_7 Race 7 to determine the 2^(nd) and 3^(rd) 7 Races are needed.

$$\mathrm{First}\:\mathrm{5}\:\mathrm{races}\:\mathrm{with}\:\mathrm{numbered}\:\mathrm{results} \\ $$$$\mathrm{1}:\:\:\mathrm{h}_{\mathrm{1}} \:\mathrm{h}_{\mathrm{2}} \:\mathrm{h}_{\mathrm{3}} \:\mathrm{h}_{\mathrm{4}} \:\mathrm{h}_{\mathrm{5}} \\ $$$$\mathrm{2}:\:\:\mathrm{h}_{\mathrm{6}} \:\mathrm{h}_{\mathrm{7}} \:\mathrm{h}_{\mathrm{8}} \:\mathrm{h}_{\mathrm{9}} \:\mathrm{h}_{\mathrm{10}} \\ $$$$\mathrm{3}:\:\mathrm{h}_{\mathrm{11}} \:\mathrm{h}_{\mathrm{12}} \:\mathrm{h}_{\mathrm{13}} \:\mathrm{h}_{\mathrm{14}} \:\mathrm{h}_{\mathrm{15}} \\ $$$$\mathrm{4}:\:\mathrm{h}_{\mathrm{16}} \:\mathrm{h}_{\mathrm{17}} \:\mathrm{h}_{\mathrm{18}} \:\mathrm{h}_{\mathrm{19}} \:\mathrm{h}_{\mathrm{20}} \\ $$$$\mathrm{5}:\:\mathrm{h}_{\mathrm{21}} \:\mathrm{h}_{\mathrm{22}} \:\mathrm{h}_{\mathrm{22}} \:\mathrm{h}_{\mathrm{24}} \:\mathrm{h}_{\mathrm{25}} \\ $$$$\mathrm{2}\:\mathrm{elimnated}\:\mathrm{from}\:\mathrm{each}\:\mathrm{group}\:\mathrm{since}\:\mathrm{they}\:\mathrm{cannot} \\ $$$$\mathrm{take}\:\mathrm{position}\:\mathrm{1}\:\mathrm{2}\:\mathrm{3}\:\mathrm{overall}. \\ $$$$\mathrm{6th}\:\mathrm{Race}\:\mathrm{with}\:\mathrm{toppers}\:\left(\mathrm{h}_{\mathrm{1}} ,\:\mathrm{h}_{\mathrm{6}} ,\:\mathrm{h}_{\mathrm{11}} ,\:\mathrm{h}_{\mathrm{16}} ,\:\mathrm{h}_{\mathrm{21}} \right) \\ $$$$\mathrm{Let}\:\mathrm{us}\:\mathrm{assume}\:\mathrm{results}\:\mathrm{are} \\ $$$$\mathrm{h}_{\mathrm{1}} \:\mathrm{h}_{\mathrm{6}} \:\mathrm{h}_{\mathrm{16}} \:\mathrm{h}_{\mathrm{21}} \:\mathrm{h}_{\mathrm{11}} \: \\ $$$$\mathrm{h}_{\mathrm{11}} /\mathrm{h}_{\mathrm{21}} \:\mathrm{is}\:\mathrm{4}/\mathrm{5}\:\mathrm{among}\:\mathrm{toppers}\:\mathrm{all}\:\mathrm{participants} \\ $$$$\:\:\:\:\:\:\mathrm{of}\:\mathrm{race}\:\mathrm{3}\:\mathrm{and}\:\mathrm{5}\:\mathrm{are}\:\mathrm{eliminated}\:\mathrm{as}\:\mathrm{they}\:\mathrm{are} \\ $$$$\:\:\:\:\:\:\mathrm{slower}\:\mathrm{than}\:\:\mathrm{at}\:\mathrm{least}\:\mathrm{4}^{{th}} \:\mathrm{position} \\ $$$$\mathrm{Leave}\:\mathrm{selection}\:\mathrm{process}\:\mathrm{limited}\:\mathrm{to} \\ $$$$\mathrm{h}_{\mathrm{1}} \:\mathrm{h}_{\mathrm{6}} \:\mathrm{h}_{\mathrm{16}} \:\mathrm{h}_{\mathrm{2}} \:\mathrm{h}_{\mathrm{3}} \:\mathrm{h}_{\mathrm{7}} \:\mathrm{h}_{\mathrm{8}} \:\mathrm{h}_{\mathrm{17}} \:\mathrm{h}_{\mathrm{18}} \\ $$$$\mathrm{h}_{\mathrm{16}} \:\mathrm{is}\:\mathrm{at}\:\mathrm{best}\:\mathrm{3}^{\mathrm{rd}} \:\mathrm{so}\:\mathrm{h}_{\mathrm{17}} \:\mathrm{and}\:\mathrm{h}_{\mathrm{18}} \:\mathrm{eliminated}. \\ $$$$\mathrm{h}_{\mathrm{1}} \:\mathrm{h}_{\mathrm{6}} \:\mathrm{h}_{\mathrm{16}} \:\mathrm{h}_{\mathrm{2}} \:\mathrm{h}_{\mathrm{3}} \:\mathrm{h}_{\mathrm{7}} \:\mathrm{h}_{\mathrm{8}} \:\: \\ $$$$\mathrm{h}_{\mathrm{6}} \:\mathrm{is}\:\mathrm{at}\:\mathrm{best}\:\mathrm{second}\:\mathrm{so}\:\mathrm{h}_{\mathrm{8}} \:\mathrm{can}\:\mathrm{be}\:\mathrm{at}\:\mathrm{best}\:\mathrm{4}^{\mathrm{th}} . \\ $$$$\mathrm{h}_{\mathrm{1}} \:\mathrm{h}_{\mathrm{6}} \:\mathrm{h}_{\mathrm{16}} \:\mathrm{h}_{\mathrm{2}} \:\mathrm{h}_{\mathrm{3}} \:\mathrm{h}_{\mathrm{7}} \: \\ $$$$\mathrm{Leaves}\:\mathrm{6}. \\ $$$$\mathrm{h}_{\mathrm{1}} \:\mathrm{is}\:\mathrm{first}\:\mathrm{so}\:\mathrm{it}\:\mathrm{is}\:\mathrm{clearly}\:\mathrm{the}\:\mathrm{first}.\:\mathrm{need}\:\mathrm{to} \\ $$$$\mathrm{find}\:\mathrm{best}\:\mathrm{2}\:\mathrm{from}\:\mathrm{remainin}\:\mathrm{5} \\ $$$$\mathrm{h}_{\mathrm{6}} \:\mathrm{h}_{\mathrm{16}} \:\mathrm{h}_{\mathrm{2}} \:\mathrm{h}_{\mathrm{3}} \:\mathrm{h}_{\mathrm{7}} \:\: \\ $$$$\mathrm{Race}\:\mathrm{7}\:\mathrm{to}\:\mathrm{determine}\:\mathrm{the}\:\mathrm{2}^{\mathrm{nd}} \:\mathrm{and}\:\mathrm{3}^{\mathrm{rd}} \\ $$$$\mathrm{7}\:\mathrm{Races}\:\mathrm{are}\:\mathrm{needed}. \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com