CS3343/3341, Fake Coin Problem

CS 3343/3341
Analysis of Algorithms
Weird Topic

Fake Coin Problem

Joke: You receive a letter predicting the winner of a basketball game to be held 5 days later. The prediction is correct, but you don't think much about it. This happens on 6 more successive weeks, for 7 correct predictions of the winner. In the next letter, the letter writer asks if you'll pay $1000 for the next winner, since you can easily get more than that back by betting. The "joke" part: A scammer sends letters to 1024 people predicting the winner of a coming game, half one way, and half the other way. To the 512 people who got a winning prediction, the scammer sends another prediction. (He forgets about those who got an incorrect prediction.) After 7 weeks, 8 people have received 7 correct predictions. These 8 get the letter asking for money for the next prediction. Endless variations of this scam happen every day.

Joke: You receive a letter predicting the winner of a basketball game to be held 5 days later. The prediction is correct, but you don't think much about it. This happens on 6 more successive weeks, for 7 correct predictions of the winner. In the next letter, the letter writer asks if you'll pay $1000 for the next winner, since you can easily get more than that back by betting.

The "joke" part: A scammer sends letters to 1024 people predicting the winner of a coming game, half one way, and half the other way. To the 512 people who got a winning prediction, the scammer sends another prediction. (He forgets about those who got an incorrect prediction.) After 7 weeks, 8 people have received 7 correct predictions. These 8 get the letter asking for money for the next prediction.

Endless variations of this scam happen every day.

The Problem:

Start with n coins, all the same except for one fake coin which is lighter than the others. We have a balance scale which lets us compare any two piles of coins, to see if they are equal or if one pile is lighter than the other (and which pile is lighter).

Assume for now that n is a power of 2, say 2¹⁰ = 1024. This becomes an obvious binary search problem. Put two piles of size 512 on the scale. Whichever pile is lighter contains the fake coin, and in exactly 10 balance weighings, we determine the coin. For n = 2^k, this requires exactly k = log₂(n) weighings. We still have to worry about dealing with an odd number during a weighing, but put that off for now.

The Weird Part:

This problem comes from the algorithm book by A. Levitin, who says "This looks ... outright boring. But wait: the interesting point here is that we can do better by dividing the coins into three piles." In this case, if n is a power of 3, say 3⁷ = 2187, divide the coins into three piles of 729. Weigh any two of the piles on the balance: either they are equal and the coin is in the third (unweighed) pile, or they are not equal and the coin is in the lighter pile. In 7 weighings we will have the fake coin. Notice that with 3 fewer weighings we handle more than twice as many coins. For n = 3^k, this requires exactly k = log₃(n) weighings.

Exercises (in a recitation):

What about n not an exact power of 3? Say in detail how you would handle this.
We improved from log₂(n) steps to log₃(n). By what factor did the number of steps improve?
Suppose we don't know whether the fake coin is heavier or lighter. Can you handle this case?

Revision date: 2012-09-13. (Please use ISO 8601, the International Standard Date and Time Notation.)