The following is a well-known puzzle.
Assume that you have twelve coins. One of them is a counterfeit which weighs differently from the others, which are real and weigh equally. Isolate the counterfeit by using a balance three times and determine whether it is heavier or lighter.
The author read it again in Prof. Haruhiko Okumura's "iroiro 2001 nen 12 gatu" (written in Japanese, the title means something like "miscellany in December 2001".
The problem we consider in this article is an extension of this puzzle.
| Problem(k, n). Assume that k is an integer more than two, and n is a positive integer. Assume that you have k coins. One of them is a counterfeit, which weighs differently from the others, which are real and weigh equally. Isolate the counterfeit by using a balance n times (and determine whether it is heavier or lighter, if possible). |
We have a necessary and sufficient condition.
|
Theorem 1.1 The Problem(k,n) has a solution if and only if n satisfies log3(2k+1) <= n, which is equivalen to k <= (3n-1)/2. There is a solution by which you can determine whether the counterfeit is heavier or lighter if and only if the equality does not hold. |
The values (3n-1)/2 for some n are as follows.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| (3n-1)/2 | 0 | 1 | 4 | 13 | 40 | 121 | 364 | 1093 |
Number the coins from 1 to k. Assume that {1,2,3|4,5,6} denotes the comparison with the coins 1, 2, 3 on the left side and the coins 4, 5, 6 on the right side of the balance. A solution is shown as a ternary tree. At each node, we assume that
+- #
+- {2|3} -+- 4-
| +- 3+
|
| +- 1+
{3|4} -+- {1|4} -+- 2?
| +- 1-
|
| +- 3-
+- {2|3} -+- 4+
+- #
The terminals, or terminal nodes,
correspond to the conclusions.
The terminal label 2? means
that the coin 2 is the counterfeit but we don't know
whether it is heavier or lighter than the real ones.
The label 1+ (resp. 1-)
means that the coin 1 is the counterfeit
which is heavier (resp. lighter)
than the real ones.
The label # means an unreachable terminal.
The next is a solution for the Problem(8,3).
+----------- 8+
|
| +- 7-
+- {3,8|2,4} -+- {5|7} -+- 6+
| | +- 5-
| |
| | +- 4+
| +- {4|2} -+- 3-
| +- #
|
| +----------- 2+
| |
| | +- 1+
{4,6,8|3,5,7} -+- {2|3} -----+- {1|2} -+- #
| | +- 1-
| |
| +----------- 2-
|
| +- #
| +- {4|2} -+- 3+
| | +- 4-
| |
| | +- 5+
+- {3,8|2,4} -+- {5|7} -+- 6-
| +- 7+
|
+----------- 8-
It is easy to verify the following fact.
| Fact 2.1 If the left side balances with the right side every time, then the conclusion must be # or i? where the coin i is the one which has never been weighed. The other conclusions must be # or i+ or i-. |
Assume that the Problem(k, n) has a solution. The number of terminals are equal to or less than 3n. If it has the conclusions i+ or i- for every i, then 2k <= 3n holds. If it has the conclusion i? for some i, then 2k-1 <= 3n holds. Anyway, we have 2k-1 <= 3n.
Assume that there is a solution if 2k-1 = 3n.
Assume that in the first weighing we compare the different number of coins. If the weight of the counterfeit differs very slightly from the one of the real coins, you can predict the result before weighing, and this solution is essentially a solution for the Problem(k, n-1). Thus we may assume that in the first weighing we compare the same number of coins.
Assume that you put k1 coins at each side of the balance in the first weighing. If the left side does not balance with the right side, we go along the upper subtree or the lower subtree. These subtrees have at most 2×3n-1 terminals. They have conclusions concerning the coins we put on the scale in the first weighing. Therefore we have 4k1 <= 2×3n-1, but the equality never holds because of the uniqueness of the prime factorization. Thus we have 4k1+2 <= 2×3n-1. Since the middle subtree has 3n-1 conclusions concerning the k-2k1 coins, we have 2(k-2k1)-1 <= 3n-1. Note that if the equality holds then the solution has the conclusion i? for some i. We have proved the following.
| Lemma 2.2 If the Problem(k, n) has a solution, then k and n satisfy the condition 2k+1 <= 3n, which is equivalent to k <= (3n-1)/2. If the equality holds, then every solution has the conclusion i? for some i. |
We label each coin as follows. Each label consists of two characters. The first character is '0' if we are sure that the coin is not heavier than the real ones. Otherwise the first character is '+'. The second character is '0' if we are sure that the coin is not lighter than the real ones. Otherwise the second character is '-'.
Before weighings, every label is "+-". After a weighing, the labels of the coins change as follows.
First, we sketch the construction.
Divide the coins into three groups and compare the second and the third group.
+0 +0 0- 0- +0 +0 0- 0-
\_____________/ \_____________/
| |
+--------^--------+
| Lemma 3.1 Let n be a non-negative ingeter. After some weighings, assume that every coin has the label "+0" or "0-" or "00" and let k be the numbers of the coins with the label "+0" or "0-". If k <= 3n holds, then you can isolate the counterfeit by n-1 more weighings. |
Proof. If n = 0, then k = 1 holds and you have already isolated the counterfeit.
Assume that n >= 1. If k = 1, then you have already isolated the counterfeit. If k = 2, compare a coin with "00" with the coin with "+0" or "0-".
Assume that k >= 3. Divide the coins with "+0" or "-0" into three groups G1, G2 and G3 such that
| k | 3j | 3j+1 | 3j+2 |
|---|---|---|---|
| G1 | j | j+1 | j |
| G2 | j | j | j+1 |
| G3 | j | j | j+1 |
This is done as follows.
The condition k <= 3n implies that the number of the coins of any group is not more than 3n-1.
Compare G2 and G3 by the balance.
Rewrite the labels according to the result and apply this Lemma again. In any case, at most n-1 more weighings suffice.
[Q.E.D.]
| Lemma 3.2 Let n be a non-negative integer. After some weighings, assume that there is at least one coin with "00" and let k be the number of coins without "00". If k <= (3n+1)/ 2, then you can isolate the counterfeit by n-1 more weighings. If the equality does not hold, you can determine whether the counterfeit is heavier or lighter than the real ones. |
Proof. If n = 0, then k = 1. In this case, the assertion is true.
Assume that n >= 1. Choose the largest odd number k1 which is equal to or smaller than both 3n-1 and k. Since both 3n-1 and k are positive integers, therefore k1 is positive, too. Divide the coins without "00" into three groups G1, G2 and G3 such that
Add one coin with "00" to G3 and compare G2 with G3 by the balance. Rewrite the labels according to the result.
[Q.E.D.]
Note: Under the hypothesis of the Lemma above, if there is a solution by which we can determine whether the counterfeit is heavier or lighter in every case, it has at least 2k conclusions. Since it has 3n terminals, it is a contradiction if the equality holds. If the equality does not hold, while we apply this Lemma repeatedly, the first group becomes empty.
Note: The values (3n+1)/2 for some n are as follows.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| (3n+1)/2 | 1 | 2 | 5 | 14 | 41 | 122 | 365 | 1094 |
| Proposition 3.3 Let n and k be integers and assume that k is more than two. If k <= (3n-1)/2, then we can isolate the counterfeit by n weighings. If the equality does not hold, you can determine whether the counterfeit is heavier or lighter than the real ones. |
Proof. Note that n >= 2. Choose the largest even number k1 which is equal to or smaller than both 3n-1-1 and k. Since 3n-1-1 >= 2 and k >= 3, therefore k1 is positive. Divide the coins into three groups G1, G2 and G3, where G2 and G3 consist of k1/2 coins respectively.
Compare G2 and G3 by the balance. Rewrite the labels according to the result.
[Q.E.D.]