Over at Time to Blog Abhay Parekh poses a problem:
The Oddball Problem: You are given n identical looking balls. n-1 of them weigh the same, but one of them is either heavier or lighter than the others (you don't know which). Given a two pan weighing machine what is the minimum number of weighings you need to do to be sure that you have identified that odd ball? You can only use the weighing pan as follows: put some balls in the left pan, some in the right pan and observe one of three possible outcomes: either the left pan is heavy or the right pan is heavy, or they are even.
Since you don't know if the odd ball is heavier or lighter things get a bit tricky. This problem is often posed with 12 balls. Here's a problem worth working on:
Show that for 12 balls you can always identify the oddball in 3 weighings!
It happens that, a few days ago, I was confronted with the 12-ball variety of the problem by the local Big Brothers Big Sisters organization, which every week, before I meet my "little" at a nearby school, sends out to the "bigs" a "suggested activity." As I worked on the problem during a boring work meeting, and then some more over my lunch break, and yet more at a coffeeshop in the afternoon, I began to question how much Big Brothers Big Sisters knows about the mental development of sixth graders and what they are apt to enjoy. I was hooked by the difficulty, however, and eventually worked out what I take to be a solution. Since my "little brother" exhibited no interest, I shall set it out here, before Abhay posts his version of a solution. If nothing else it is an interesting exercise in "technical" writing.
For ease of exposition, let us think of the balls as being numbered 1 through 12. Begin by weighing 1, 2, 3 and 4 against 5, 6, 7 and 8. Suppose they balance. You now know that the "oddball" is 9, 10, 11 or 12. Use the second trial to weigh, say, 1, 2 and 3 against 9, 10 and 11. If the result is another balance, you know the "oddball" is 12, and it is a simple matter to use the third trial to determine whether it is heavier or lighter than the rest. But suppose 1, 2 and 3 are, for example, lighter than 9, 10 and 11. That could only mean that 9, 10 or 11 is the "oddball" and heavier than the rest. On the last trial, weigh 9 against 10. If they balance, 11 is odd (and heavy). If they don't balance, the heavier one is the "oddball."
Now we need to consider the case where, on the first trial, 1, 2, 3 and 4 do not balance with 5, 6, 7 and 8. If, for example, 1, 2, 3 and 4 are lighter than 5, 6, 7 and 8, we know that either 1, 2, 3 or 4 is the "oddball" (and light) or 5, 6, 7 or 8 is the "oddball" (and heavy). On the second trial, weigh 1, 2, 3 and 5 against 4, 9, 10 and 11. Suppose that 1, 2, 3 and 5 are lighter. Since 5 cannot be light and 4, 9, 10 and 11 cannot be heavy (refer to result of the first trial), this means that 1, 2 or 3 is the oddball (and light). Weighing 1 against 2 on the third trial will reveal which of those three is the (light) "oddball."
We have yet to consider the case where 1, 2, 3 and 5 balance 4, 9, 10 and 11 and the case where 1, 2, 3 and 5 are heavier than 4, 9, 10 and 11. In the former case, we learn that 6, 7 or 8 must be the "oddball" (and heavy). Use the third trial to weigh 6 against 7, which will suffice to reveal which of those three is heavier than the other twelve. In the latter case, we learn that either 5 is odd (and heavy) or 4 is odd (and light). The solution is clear if on the third trial either 4 or 5 is weighed against any one of the ten that we know are not the "oddball": if, for example, 4 balances with 1, then 5 is odd (and heavy), whereas if 4 is lighter than 1 then 4 is the (light) "oddball."
Comments