You have eight pennies that look the same, but one is counterfeit. The counterfeit penny is known to be heavier than the others. How can you tell which one is counterfeit by using a balance scale only twice? (The balance scale has two pans but no weights; you can place any combination of pennies in either pan and then observe whether the pennies in each pan weigh the same, or if one collection is heavier than the other.)

The original question did not include the information that the counterfeit penny is heavier, but without that information not even the MathNerds could do it. Can you?

Hint 1

Start small. Try to solve this problem instead: You have 3 pennies, and one is counterfeit and heavier than the others. Find it in one weighing. (If this is too hard, start even smaller: suppose you only have 2 pennies; find the counterfeit in one weighing.)

Hint 2

With three pennies, the only reasonable thing you can do is pick any two of them and put one in each pan. There are three possibilities:

left pan is heavy
the pans balance
right pan is heavy

Explain how you can deduce the heavy coin in each case.

Hint 3

The first and third cases are easy: we know the counterfeit coin is heavy, so the pan that is heavy has the counterfeit coin. The second case is only a little harder: there's only one counterfeit coin, so at least one of the two coins in the pans is not counterfeit, and because the other coin weighs the same, it is not counterfeit either. Therefore by a process of elimination the third coin (the one not in the pans) is counterfeit.

We started small and solved the small problem, now let's try to leverage that solution to solve a bigger problem. Explain how to perform two weighings on eight coins, so that the last weighing matches the step we used for three coins.

The Rest of the Solution

To apply the solution for three coins, we need to isolate the counterfeit coin to a group of three coins, using only one weighing, and in fact we can use the same idea. Divide the eight coins into groups of three (one group will only have two), then balance the two groups of three against each other. Just as in the three-coin problem, if one side is heavier, it contains the counterfeit coin, and if the sides balance, the other group of two coins contains the counterfeit coin. If one of the groups of three contains the counterfeit, we can find it in one more weighing using the three-coin solution. If the other group of two contains the counterfeit, we can find it in one more weighing by balancing the two coins against each other.

Notice that we could have isolated a counterfeit coin in two weighings even if we were given nine coins instead of eight, but if there were ten coins we could not have found the counterfeit by this method. Can you guess a generalization of this method? How large a collection of coins could you handle in N weighings?

What If The Counterfeit Could Be Heavy Or Light? The Twelve Coins Problem

What if we only knew that the counterfeit coin was a different weight that the true coins, so it might be heavier or lighter? Could we still find it? If we knew it was lighter, we could use the same method (except that we would pick the lighter side as counterfeit instead of the heavier side), but if we only knew the counterfeit was a different weight, we couldn't use the same method. In the three-coin problem, if the pans balanced we would know the third coin was counterfeit, but if the pans did not balance we would only know that one of the two was counterfeit, but not which one.

It turns out that there are methods for this problem too, but they are harder to discover. This problem is often stated as the Twelve Coins or Twelve Bags of Gold, where you have twelve items and must discover the false item in three weighings. See if you can discover a method for this. Starting small is still a good idea, so start by discovering how to isolate the counterfeit out of three coins using two weighings. In general you won't be able to narrow down the false item until the end, so you should think of the weighings as methods for collecting information about collections of coins, where at the end you will put together all the information and draw a conclusion.

This problem is written up in another Best of MathNerds article: The Twelve Coins (or Twelve Bags of Gold).

Another Popular Balance Problem

Show that using four known weights of your choice, you can weigh any number of pounds, from one through forty pounds. You put the item to be weighed in one pan, and you are allowed to place known weights in either pan; they don't have to all be in the other pan. Hint: Start small. Show that with two known weights you can measure one through four pounds. Another hint: Many balance problems (including the ones we have looked at here) involve ternary (base 3) arithmetic, either implictly or explicitly, because there are three possible outcomes to each weighing.

References

The Cut The Knot! web site gives several solutions to the Twelve Coins problem: by Brian D. Bundy, by Donald J. Newman, by W. McWorter (he also gives a solution to the four-weights problem), and by Jack Wert. When reading these solutions it helps to write out the method for the three-coin, two weighings version because it is much easier to understand than the full twelve-coin version. Newman's solution is the most straightforward, but his explanation is very concise, so you'll still have to work to understand it.
Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics. Addison-Wesley, 2nd edition, 1994. On page 2 we find "we'll see repeatedly in this book that it's advantageous to LOOK AT SMALL CASES first". Many mathematical puzzles (and even serious problems) are overwhelming because of the number of items involved; see if you can state a similar problem using smaller numbers and solve that, as we did here with the number of coins. This is helpful for nearly any puzzle that involves a large number of things, such as the Towers of Hanoi (64 disks), the Locker Problem (1000 lockers), finding the sum of the first 100 integers, and many more. Do not stubbornly say "My job is to solve 8 coins, do not distract me with 3-coin problems."