The Impossible Question2

:: Context (Would I move Mt. Fuji?) ::

---

I couldn’t help wondering if I ever was in Gene McKenna’s shoes for this interview with Microsoft…

The Interview Scene (excerpt from the book):

Suppose you had eight billiard balls, the recruiter began. One of them is slightly heavier, but the only way to tell is by putting it on a scale against the others. What’s the fewest number of times you’d have to use the scale to find the heavier ball?

I shouldn’t deny the fact here that I am not facing this kind of question for the first time . I first heard a similar kind from one of my close friend who was proudly eliciting his success on an interview with Infosys. Well! now you see the line of corporations who has joined this “recruitment-methodology” band-wagon. So, I was kind of ready for this one. I have this habit (good as well as bad) of manipulating similar problems, imparting to it the “larger than life” image that I like to confront, just for the sake of personal joy and satisfaction. And I ended up wondering thus:

Suppose if it wasn’t known if the odd ball in the set was either heavier or lighter, what’s the fewest number of times one would have to use the scale to find the odd one?

Please give it a try if you haven’t, before you read my take on both. To start with, i have highlighted (bold and italicised) the key words that matter.

:: My Take On It ::

---

:: Take 1::
There are different solutions to this problem. “Divide and Conquer” is the key solution to this problem. But, how would you divide to make the conquest complete in the shortest possible moves?
Sets of 3 or its multiples are ideal in terms of elimination, in this case, as the last set would be reduced to just 3 and with just one weighing we can isolate the heavier/lighter ball. Let me explain it further. If the heavier/lighter ball is one among the 2 that is weighed, the heavier/lighter
scale indicates the heavier/lighter ball whereas if they weigh the same, then the third ball that is not weighed is the heavier/lighter one. On this account, let us try to divide these 8 balls into sets of 3 which leaves us with three sets namely A, B & C with 3, 3 & 2 balls respectively. The heavier ball in our case should lie in any of these 3 (A, B & C) sets.

Step 1 would be to determine this set. The easiest way is to weigh sets A & B of three balls each.

• If A weighs more, the heavier ball is in set A
• If B weighs more, the heavier ball is in set B
• And if A & B weighs equal, the heavier ball is in set C

Step 2 would be to determine the heavier ball as we have reached the final set by now. And as explained earlier, we know how to determine the heavier ball from a set of 3 (A or B) with just one weighing. And of course, to the get the heavier ball from set C is just direct weighing.

:: So in just 2 weighing (cumulative weighing from step 1 through 2), we can determine the heavier/lighter ball ::

:: Take 2 ::
Now consider the case when we don’t know if the odd ball is heavier or lighter than the rest. Divide and Conquer principle applies here as well.

Figure 1 below shows the division of balls into various sets (A through H) for determining the odd ball in the most optimal number of weighings. The dotted lines indicate how sets G & H are derived (the details are available in Figure2):

Figure 1

Figure 2 below depicts the complete flow chart for determining the odd ball in the most optimal number of weighings:

Figure 2

:: So in just 3 weighing, we can determine the heavier/lighter ball ::

The Impossible Question1

:: Context (Would I move Mt. Fuji?) ::

---

This was one of those moments when I felt at least for a second that I was an older Jim Gibbons (1) in my early thirties, in front of the great William Shockley (2). What really fascinated me was that the reasoning that I had applied for the solution had striking similarity with the reasoning of the then, interviewer (2) and interviewee (1).

The Interview Scene (original excerpt from the book):

Shockley picked up his stopwatch.
There’s a tennis tournament with one hundred twenty-seven players, Shockley began, in measured tones. You’ve got one hundred twenty-six people paired off in sixty-three matches, plus one unpaired player as a bye. In the next round, there are sixty-four players and thirty-two matches.
How many matches, total, does it take to determine a winner?
Shockley started the stopwatch.

Though it’s said think twice (or more) before you do something, I think one needs to understand well “what” one is trying to do rather that worrying “how”, from the word “GO”. I guess that’s how i landed a knock-out in the first round.

Please give it a try if you haven’t, before you read my take on it…

:: My Take On It ::

---

Shockley was just setting the stage for Gibbons as indicated clearly by the strike-through lines. This is a diversion from the actual problem inducing unwanted complexities to the actual problem problem at hand. Now comes the real kill; the statements underlined will definitely take the interviewee off course on a wild-goose chase (though in this case would definitely lead you to the answer but not quick enough to beat Shockley’s stopwatch), but it discretely conveys the random knock-out nature of the tournament which is a key attribute in determining the solution. So, the final problem statement gets almost reduced to the “italic statements in bold”.

Shockley picked up his stopwatch.
There’s a tennis tournament with one hundred twenty-seven players, Shockley began, in measured tones. You’ve got one hundred twenty-six people paired off in sixty-three matches, plus one unpaired player as a bye. In the next round, there are sixty-four players and thirty-two matches.
How many matches, total, does it take to determine a winner?
Shockley started the stopwatch.

The answer is now lying open in front of you:

:: To determine a fair winner all others would have to be eliminated in this knock-out tournament which leaves us with 126 matches ::

Now the mathematical derivation which Shockley would have liked Gibbons to do based on his underlined statements:

• 126 players -> 63 matches (A)
• 064 players -> 32 matches (B)
• 032 players -> 16 matches (C)
• 016 players -> 08 matches (D)
• 008 players -> 04 matches (E)
• 004 players -> 02 matches (F)
• 002 players -> 01 matches (G)

Ans: A+B+C+D+E+F+G :: 63+32+16+8+4+2+1 = 126 matches

Would I move Mt. Fuji?

Would I? Well, I don’t know yet. But I intend to put an earnest effort by trying out random “problems” that are outlined in this great book (“How would you move Mt. Fuji?” by William Poundstone). A big thanks goes to a good friend Nikhil who lent me this book, thus inspiring me to blog my take on it.

The solutions and approach would be entirely based on “personal” reasoning and interpretations. And this would be NO reference for anyone seeking answers to those problems unless I confidently claim “so”.