When Google is interviewing potential employees they are given a series of seemingly outrageous questions to test their problem solving ability. How many piano tuners are in the world? How would you design an evacuation plan for San Francisco? Why are manhole covers round?
The full list of revealed questions can be found on this website: http://www.impactinterview.com/2009/10/140-google-interview-questions/
A functional knowledge of mathematics is needed to know how to approach these problems, and some are rooted in famous math historical questions. The piano tuners question is a Fermi Problem, named after Enrico Fermi, who posed many estimation problems with little information and had startlingly accurate results. (I plan to simulate a Fermi Problem in a future post). On another note, I once attended a seminar at a math conference where the guest speaker spoke entirely about the manhole problem and its extensions.
The problem I would like to look at today from Google is the following:
- You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?
I highly encourage to spend some time attempting to solve it before reading onward – its challenging, but can be done with some thought.
Here’s how I went about solving it:
- Start with weighing 6 of the balls – 3 on each side of the scale.
- If the scale is perfectly balanced, then weigh the remaining 2 and find the one that is heavier.
- If the scale was not balanced, then take the 3 balls from the heavier side.
- Weigh 2 of them.
- Either the heavier one will be identified, or if they are balanced then the remaining one is heaviest
I kept thinking about this problem for another week and wanted to investigate further. What is the maximum number of balls where a heavier one could be identified in two weighings? What about three weighings?
My approach was to solve for a certain number of cases and see if a pattern would appear that would predict the number of balls versus weighings needed.
Some cases were trivial, such as with 1, 2, or 3 balls. At 4 for the first time you would need to do a second weighing. 5, 6, 7, 8, and 9 followed suit. To describe it, with 9 balls your first weighing would be between two sets of 3 balls. The outcome (the scale revealing the heavier set or balancing to reveal it was the unmeasured ones) would whittle down the possibilities to 3 balls. The second weighing would determine which one it was.
At 10 balls you finally need a third weighing, and the reason why ties into the groupings. I realized that a key component to this problem is that the process of weighing separates the balls into three groups. Thus, the number of weighings increases each time the number of balls surpasses a power of 3. Below is a table that shows select cases that demonstrate this transition.
| # of Balls | # of Weighings |
| 3 | 1 |
| 4 | 2 |
| 8 | 2 |
| 9 | 2 |
| 10 | 3 |
| 26 | 3 |
| 27 | 3 |
| 28 | 4 |
Using this information I was able to find an equation to help illustrate this. By inputting the number of balls, b, you can find the maximum number of weighings, w, required to single out a heavier one.
And using it, I could find out the number of weighings for ridiculous numbers of balls.
| # of Balls | # of Weighings |
| 100 | 5 |
| 12345 | 9 |
| 999999 | 13 |
| 1000000 | 13 |
All the Calculations 