InterviewSolution
Saved Bookmarks
InterviewSolution
| 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» Solution :Note : The faceoffs are independent of each other (their hungers will have their initialvalues before each faceoff). at least 7 matches are needed. Denote the players by A, B, C, D and E. 1. First, A playsagainst B, while C plays against D. Without loss of generality, suppose Aand C are the winners. 2. Then, let A play C in the winners’ match. Without loss of generality, suppose A WINS. Upto this point, we have determined that A gt B and A gt C gt D. 3. Now, we determine the position of E within the A gt C gt D CHAIN. 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 ORDERING 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 PRODUCED 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, ASSUME 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. In all cases, we have determined the complete ordering in 7 matches. |
|