6
Find That Fake
When you see a fork in the road, take it.
—Yogi Berra
Programming constructs and algorithmic paradigms covered in this puzzle: Case analysis. Divide and conquer.
There are lots of popular puzzles about finding a counterfeit coin in a set of coins using only a weight balance. One variant is as follows: Find a fake coin in a set of nine identical-looking coins. You know that the fake coin is heavier than the rest. Your goal is to minimize the number of weighings.
The coins look identical and the fake is only slightly heavier than the rest. So if you put a differing number of coins on either side of the balance, the balance will never say that the two sides are equal. (Balance shown below.)
How many weighings do you need?
Given nine coins, of which eight are identical and one is slightly heavier, we can imagine choosing a coin arbitrarily and comparing it with each of the other eight coins. This guarantees that we will find the fake in eight weighings.
However, we can do much better through a process of aggregating coins and comparing collections of coins. Rather than eliminating one coin at a time as in the iterative solution above, we can eliminate many coins from consideration with one weighing. The strategy we will use falls into the category of divide-and-conquer approaches to puzzles and other problems.
Divide and Conquer
Suppose we pick four coins from the set of nine, and split them into two pairs of coins. If we weigh the pairs against each other, we have three possibilities:
- The pairs are equal in weight. This means that none of these four coins is a fake, and the fake is in the remaining five coins.
- The first pair is heavier. This means that one of the coins in this pair is a fake. We can determine which one is fake by comparing the coins in the first pair.
- The second pair is heavier. This situation is similar to case 2 above.
In cases 2 and 3 we can determine the fake coin using two weighings.
In case 1, after one weighing we are left with five coins, and one of these five is a fake. Let’s arbitrarily pick four coins out of the five and repeat the process. This second weighing of two versus two can result in three cases, just like the first. We will refer to these cases as case 1.1, case 1.2, and case 1.3. The 1 means the first weighing resulted in case 1, and the .1, .2, and .3 suffixes correspond to cases resulting from the second weighing.
In the second weighing, if the two pairs are equal in weight—case 1.1—the fake coin is indubitably the coin we did not pick, and we have found it in two weighings.
Case 1.2 is the case where the first pair is heavier. After two weighings, we are not done yet. We still have to compare one coin against another, and this third weighing will tell us which one is fake. The same analysis holds for case 1.3. Three weighings to find the fake in the worst case is much better than eight, but is it optimal?
Suppose we pick two sets of three coins each from the initial set of nine coins. Let’s compare their weights. As before, we have three cases:
- The sets are equal in weight. This means that none of these six coins is a fake, and the fake is in the remaining three coins.
- The first set is heavier. This means that one of the coins in this pair is a fake.
- The second set is heavier. This situation is similar to case 2 above.
This divide-and-conquer strategy is much more symmetric. In all three cases we have identified a set of three coins that has the fake. This has reduced the number of coins we have to deal with from nine to three using only one weighing. If we split the three coins into three sets of one coin each, and repeat this process, after the second weighing we will have determined the fake coin.
Let’s say we have nine coins, numbered 0 through 8, and coin 4 is the fake. We will compare coins 0, 1, and 2 against 3, 4, and 5, and discover that 3, 4, and 5 are heavier. This is case 3 above. We will compare coin 3 versus 4 and discover that 4 is heavier, and therefore the fake.
Recursive Divide and Conquer
What happens if you have more than nine coins? Suppose we have twenty-seven coins and one of them is a fake, and slightly heavier. We split the coins into three groups of nine coins each. We follow the strategy above and find the group of nine that is heaviest. This is a group of nine with one fake coin, and we just solved that problem using two weighings. So we need only one more weighing to find a fake in twenty-seven coins, as compared to finding a fake in nine coins. As you can see, this divide-and-conquer strategy is very powerful, and we will keep returning to it in various puzzles, including the next one.
Now, let’s write a program to solve the fake coin problem. In this particular instance of moving from the physical world to the virtual world of computer programs, we will have to pretend that we can’t do something we really can. More on that later.
Given groups of coins, we can compare two groups to determine which one is heavier or whether they are equal. The function below is our weight balance.
1. def compare(groupA, groupB):
2. if sum(groupA) > sum(groupB):
3. result = 'left'
4. elif sum(groupB) > sum(groupA):
5. result = 'right'
6. elif sum(groupB) == sum(groupA):
7. result = 'equal'
8. return result
The function sum simply adds up the elements of the argument list and returns the sum. The function compare tells us whether the left side is heavier, the right side is heavier, or the sides are equal. Note that on line 6 we have an elif where an else would suffice. If the predicates for the if (line 2) and the first elif (line 4) are not true, then the groups will have equal weight. We used an elif on line 6 to explicitly indicate that this case corresponds to the two groups having equal weight.
Given a list of coins, we can split the list into three equal-sized groups. We will assume that the number of coins in the argument list for the following function is 3n for some n.
1. def splitCoins(coinsList):
2. length = len(coinsList)
3. group1 = coinsList[0:length//3]
4. group2 = coinsList[length//3:length//3*2]
5. group3 = coinsList[length//3*2:length]
6. return group1, group2, group3
Lines 3–5 split the list into three different sublists using integer division and the slice operation in Python. The operator // is integer division, for example, 1//3 = 0, 7//3 = 2, 9//3 = 3, and 11//3 = 3. Recall that if we have b = a[0:3], the first three elements of a are copied into list b, which will have length 3. (We will assume that list a has length at least 3.) In lines 3–5, the first third of the list coinsList is copied to group1, the second third to group2, and the last third to group3. Line 4 is the most complex: If length is 9, then length//3 = 3, length//3*2 = 3*2 = 6, since // takes precedence over *.
All these sublists are returned (line 6).
The following function does one comparison, that is, one weighing (line 2), and determines which group has the fake coin based on the result. The function assumes that the fake coin is heavier than the other coins, which are all identical.
1. def findFakeGroup(group1, group2, group3):
2. result1and2 = compare(group1, group2)
3. if result1and2 == 'left':
4. fakeGroup = group1
5. elif result1and2 == 'right':
6. fakeGroup = group2
7. elif result1and2 == 'equal':
8. fakeGroup = group3
9. return fakeGroup
If the left side is heavier (line 3), then the first group contains the fake coin (case 2 of the algorithm). If the right side is heavier (line 5), then the second group contains the fake coin (case 3). If the two sides are equal (line 7), then the fake coin is contained in the third group (case 1). Note that we again used an elif where an else would suffice, on line 7.
Now we are ready to code our divide-and-conquer algorithm, which finds the fake coin in a list of 3n coins whose weights are contained in the argument coinsList.
1. def CoinComparison(coinsList):
2. counter = 0
3. currList = coinsList
4. while len(currList) > 1:
5. group1, group2, group3 = splitCoins(currList)
6. currList = findFakeGroup(group1, group2, group3)
7. counter += 1
8. fake = currList[0]
9. print ('The fake coin is coin',
coinsList.index(fake) + 1,
'in the original list')
10. print ('Number of weighings:', counter)
Line 2 initializes the variable counter, which counts the number of weighings that will be performed. Line 3 simply creates a new reference to coinsList that will be used to point to the current collection of coins under consideration. Lines 4–7 correspond to the divide-and-conquer strategy that shrinks coinsList to a third of its size at each iteration. When the size of currList is 1, we have found the fake. The algorithm is as described earlier—split coins into three groups in splitCoins, then determine the group with the fake coin by comparing group1 to group2.
At line 8 we have exited the while loop, implying len(currList) is 1 (assuming it was 3n for some n to begin with). We then print out the position of the fake coin in coinsList and the number of weighings given by the value of counter.
Let’s say we have the set of coins represented by coinsList below:
coinsList = [10, 10, 10, 10, 10, 10, 11, 10, 10,
10, 10, 10, 10, 10, 10, 10, 10, 10,
10, 10, 10, 10, 10, 10, 10, 10, 10]
If we run:
CoinComparison(coinsList)
We get:
The fake coin is coin 7 in the original list
Number of weighings: 3
How is this fake found? In the first weighing in the call to findFakeGroup we compare the first row of nine coins in coinsList, that is, group1, with the second row, group2. The balance will return 'left' and therefore the group chosen is group1. In the next weighing, the first three coins of the first row of coinsList are compared against the next three. Since these are equal, findFakeGroup will return group3, that is, the last three coins. The last weighing compares the fake coin against an authentic one and returns 'left', and thus we find the fake.
We can just look at each of the elements of coinsList and determine which coin is heaviest by scanning the list and comparing numeric values. However, this will require—in the worst case—looking at each coin and comparing values to find the one value different from all others. Our divide-and-conquer algorithm is designed to minimize the number of comparisons because we assume in this puzzle that comparisons using the weight balance are expensive. For example, coinsList may be a data structure that costs a lot to access since it is stored in a faraway computer. All the faraway computer can do is compare sets of coins that you specify and tell you which set is heavier. Transmission of information between your local computer and the faraway computer is expensive, and needs to be kept to a minimum.
What if you didn’t know whether the coin was heavier or lighter in findFakeGroup? We need to write a findFakeGroupAndType function. Below is what you have to do for the case of result1and2 == 'left', that is, the case where group1 is heavier than group2 in findFakeGroupAndType. The other cases will need similar modifications.
1. if result1and2 == 'left':
2. result1and3 = compare(group1, group3)
3. if result1and3 == 'left':
4. fakeGroup = group1
5. type = 'heavier'
6. elif result1and3 == 'equal':
7. fakeGroup = group2
8. type = 'lighter'
When group1 is heavier than group2, we compare group1 and group3 (line 2). If group1 is heavier than group3, it is clear that group1 contains the fake and the fake is heavier than the genuine coin. If group1 is equal in weight to group2 (line 6), then group2 contains the fake and the fake is lighter than the genuine coin. Note that if there is exactly one fake (that is lighter or heavier) we can’t have result1and3 == 'right', because this means that group1 is heavier than group2, and that group3 is heavier than group1 and group2 by transitivity, which is a contradiction, since we are guaranteed with exactly one fake that two groups will have equal total weight.
Fortunately you only have to do this extra work once, right at the beginning. In two weighings you find a group that is one-third the size of the coin collection you are given, and you know whether the fake in the group is heavier or lighter. Then you can proceed as before. Of course, if we know the coin is lighter, we need to return a different group than what is returned by findFakeGroup, which assumes the fake coin is heavier.
Therefore, if you have 3n coins and one of them is fake, and is lighter or heavier, but you don’t know which, you only need n + 1 weighings to determine the fake coin. Fleshing out the described strategy is one of the exercises of this puzzle chapter.
Ternary Representation
The non-decimal number representation was very helpful in the crystal ball puzzle (puzzle 5), and it is natural to ask whether such a representation can be used to solve our fake coin problem. Assume we have 3n coins. We’ll use a ternary representation, and the coins will be numbered from 0 to 3n − 1 with the numbers represented in ternary. If n = 4, the first coin is represented as 0000 and the last one as 2222. For the first weighing, we will simply select three groups of coins corresponding to the first digit in the representation being a 0, 1, and 2. Each group in this first weighing will have nine coins. Let’s assume we determine that the fake coin is in the 2 pile. For the second weighing, we will select the three groups corresponding to the first two digits being 20, 21, and 22. Four weighings will specify all four digits, for example producing 2122, meaning that we are down to one coin, the fake one.
A Popular Variant Weighing Puzzle
Suppose we have twelve coins that look identical, but one is fake and is slightly heavier or lighter than the others—you don’t know which. Can you find out which one is fake using at most three weighings? This problem is obviously more difficult than the nine-coins puzzle since there are more coins. Our algorithm takes three weighings for nine coins. You will have to compare differing numbers of coins and repeatedly weigh some coins.
Exercises
Exercise 1: The code assumes there is one coin that is heavier than the rest. Given a coins list where all coins have the same weight, it claims that coin 1 is the fake. Fix the code so it does the right thing and says that none of the coins are fake.
Puzzle Exercise 2: Write CoinComparisonGeneral, which can determine the fake without assuming that the fake is heavier, as the current code does. This will involve filling in the other two cases for result1and2 in findFakeGroupAndType and then calling findFakeGroupAndType for the first split, and either findFakeGroupHeavier or findFakeGroupLighter for the remaining splits. The given procedure findFakeGroup assumes that the fake coin is heavier, and you will need to write a companion procedure that assumes the fake coin is lighter and returns the appropriate group. Your code should handle the case of there being no fake coin.
Puzzle Exercise 3: Suppose there are two fake coins, which are identical and heavier than the rest. Modify CoinComparison to find one of the fake coins—it doesn’t matter which one. Note that if you have two groups of coins, with each group having a fake, the balance is going to say that the groups are equal in weight. If you pick the third group (that was not in the comparison) you will miss finding the fake. Don’t bother with correctly counting the number of weighings in your modified code.