1.

As he reaches the exit of the market, Mario notices five people who are gathered for an eat-as-much-as-you-can competition. There is a clear order in their hunger (i.e. no two people are identically hungry) and the person who was more hungry initially (at the beginning of the competition) wins in a face-off. How many face-offs are required to rank everyone according to their initial hunger? Note : Face-offs should be sufficient to guarentee rank of everyone in any case

Answer» <html><body><p></p>Solution :Note ​ : ​ The face­offs are independent of each other ​(their hungers will have their initialvalues before each faceoff). <br/>at least 7 matches are needed.<br/> Denote the players by A, B, C, D and E.<br/>1. First, A playsagainst B, while C plays against D. Without loss of generality, suppose Aand C are the winners.<br/> 2. Then, let A play C in the winners’ match. Without loss of generality, suppose A <a href="https://interviewquestions.tuteehub.com/tag/wins-1457622" style="font-weight:bold;" target="_blank" title="Click to know more about WINS">WINS</a>. Upto this point, we have determined that A gt B and A gt C gt D.<br/> 3. Now, we determine the position of E within the A gt C gt D <a href="https://interviewquestions.tuteehub.com/tag/chain-913601" style="font-weight:bold;" target="_blank" title="Click to know more about CHAIN">CHAIN</a>. This can be achieved intwo matches. First let E play against C. If E wins, then let him play against A. Otherwise lethim play against D. After this, we have a complete <a href="https://interviewquestions.tuteehub.com/tag/ordering-1138380" style="font-weight:bold;" target="_blank" title="Click to know more about ORDERING">ORDERING</a> of A, C, D and E.4. Finally we have to find the position of B using only two more matches.So far we only have A gt B. There are two cases. If the previous step <a href="https://interviewquestions.tuteehub.com/tag/produced-592947" style="font-weight:bold;" target="_blank" title="Click to know more about PRODUCED">PRODUCED</a> E gt A gt C gt D.Then we can simply play B against C and D to complete the ordering. If A gt E occurs instead,then we may, without loss of generality, <a href="https://interviewquestions.tuteehub.com/tag/assume-384429" style="font-weight:bold;" target="_blank" title="Click to know more about ASSUME">ASSUME</a> that A gt E gt C gt D since none of E, C or Dhave played against B. Now we can simply repeat the method used in the previous step tofind the position of B amongst E gt C gt D, by first matching B against C, then E or Ddepending on the outcome.<br/>In all cases, we have determined the complete ordering in 7 matches.</body></html>


Discussion

No Comment Found

Related InterviewSolutions