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 log_{3}(2k+1) <= n, which is equivalen to k <= (3^{n}-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 (3^{n}-1)/2 for some n are as follows.
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
(3^{n}-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 3^{n}. If it has the conclusions i+ or i- for every i, then 2k <= 3^{n} holds. If it has the conclusion i? for some i, then 2k-1 <= 3^{n} holds. Anyway, we have 2k-1 <= 3^{n}.
Assume that there is a solution if 2k-1 = 3^{n}.
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 k_{1} 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×3^{n-1} terminals. They have conclusions concerning the coins we put on the scale in the first weighing. Therefore we have 4k_{1} <= 2×3^{n-1}, but the equality never holds because of the uniqueness of the prime factorization. Thus we have 4k_{1}+2 <= 2×3^{n-1}. Since the middle subtree has 3^{n-1} conclusions concerning the k-2k_{1} coins, we have 2(k-2k_{1})-1 <= 3^{n-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 <= 3^{n}, which is equivalent to k <= (3^{n}-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 <= 3^{n} 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 G_{1}, G_{2} and G_{3} such that
k | 3j | 3j+1 | 3j+2 |
---|---|---|---|
G_{1} | j | j+1 | j |
G_{2} | j | j | j+1 |
G_{3} | j | j | j+1 |
This is done as follows.
The condition k <= 3^{n} implies that the number of the coins of any group is not more than 3^{n-1}.
Compare G_{2} and G_{3} 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 <= (3^{n}+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 k_{1} which is equal to or smaller than both 3^{n-1} and k. Since both 3^{n-1} and k are positive integers, therefore k_{1} is positive, too. Divide the coins without "00" into three groups G_{1}, G_{2} and G_{3} such that
Add one coin with "00" to G_{3} and compare G_{2} with G_{3} 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 3^{n} 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 (3^{n}+1)/2 for some n are as follows.
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
(3^{n}+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 <= (3^{n}-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 k_{1} which is equal to or smaller than both 3^{n-1}-1 and k. Since 3^{n-1}-1 >= 2 and k >= 3, therefore k_{1} is positive. Divide the coins into three groups G_{1}, G_{2} and G_{3}, where G_{2} and G_{3} consist of k_{1}/2 coins respectively.
Compare G_{2} and G_{3} by the balance. Rewrite the labels according to the result.
[Q.E.D.]