The Problem of Weighing Coins with Balance.

    28 Apr, 2024

    The 'Coin Weight Problem' aims to solve the following mathematical problem: Among N coins, one coin has a different weight. with a balance scale, ensure finding the different coin with the fewest number of weighings.

    Problem Statement

    The weighing coin problem can be summarized into the following three variations:

    1. Given NN coins, one of which is heavier (or lighter) than the others. Using a balance scale, what is the minimum number of weighings needed to guarantee finding the heavier (or lighter) coin?
    2. Given NN coins, one of which has a different weight than the others. Using a balance scale, what is the minimum number of weighings needed to guarantee finding the coin with the different weight and determining whether it is heavier or lighter?
    3. Given NN coins, one of which has a different weight than the others. Using a balance scale, what is the minimum number of weighings needed to guarantee finding the coin with the different weight without determining whether it is heavier or lighter?

    For these three problems, the answers are different. The answer to the first problem is log3N⌈\log_{3}N⌉ (where x⌈ x ⌉ denotes rounding xx up to the nearest integer). The answer to the second problem is log3(2N+3)⌈\log_{3}(2N+3)⌉, and the answer to the third problem is log3(2N+1)⌈\log_{3}(2N+1)⌉.

    In other words, using the balance scale kk times, we can distinguish between 3k3^k, 3k32\frac{3^k-3}{2}, and 3k12\frac{3^k-1}{2} coins respectively.

    The first problem is relatively simple. Since we know whether the problem coin is heavier or lighter, by putting approximately 13\frac{1}{3} (rounding up or down) of the coins on each side of the balance scale in each weighing, we can reduce the range of the problem coin to one-third of its previous range. We won't go into further detail here. We mainly discuss the other two problems.

    Strict Proof

    Here we strictly prove: By using the balance scale kk times, we can distinguish among at most 3k32\frac{3^k-3}{2} coins and determine whether the problem coin is heavier or lighter.

    Let LiL_i be the set of possibly lighter coins after the iith weighing, and HiH_i be the set of possibly heavier coins.

    If we know the problem coin and its weight after kk weighings, then:

    card(Lk)+card(Hk)1\text{card}(L_k) + \text{card}(H_k) \leq 1

    where card(X)\text{card}(X) denotes the number of elements in set XX.

    Considering the kkth weighing, there are only three possible outcomes: left side heavier, right side heavier, or balanced. So, before the kkth weighing, the number of possibly problem coins can be at most 33, which means:

    card(Lk1)+card(Hk1)3\text{card}(L_{k-1}) + \text{card}(H_{k-1}) \leq 3

    This conclusion can be recursively generalized:

    card(Lki)+card(Hki)3i\text{card}(L_{k-i}) + \text{card}(H_{k-i}) \leq 3^{i}

    where 1ik11\leq i\leq k-1.

    Therefore, after the first weighing, we have:

    card(L1)+card(H1)3k1\text{card}(L_{1}) + \text{card}(H_{1}) \leq 3^{k-1}

    After the first weighing, suppose we put aa coins on each side of the balance scale, and bb coins are not on the scale, making a total of 2a+b2a+b coins.

    • If the scale is unbalanced, then either the heavier side or the lighter side contains the problem coin, so a+a3k1a+a\leq 3^{k-1}.
    • If the scale is balanced, among the remaining bb coins, there is a lighter or heavier coin, so b+b3k1b+b\leq 3^{k-1}.

    Thus, we have:

    a3k12b3k12a \leq \frac{3^{k-1}}{2} \\ b \leq \frac{3^{k-1}}{2}

    Considering aa and bb are both integers, we have:

    a3k112b3k112a \leq \frac{3^{k-1}-1}{2} \\ b \leq \frac{3^{k-1}-1}{2}

    Therefore:

    N(k)=2a+b3k32N(k) = 2a+b \leq \frac{3^k-3}{2}

    Q.E.D.Q.E.D.

    Furthermore, we consider the third question: if we don't need to determine whether the problem coin is heavier or lighter.

    In this case, LkL_k and HkH_k can each only contain one coin.

    In this situation, it's still true that after kk weighings, if we haven't placed the problem coin on the balance scale (otherwise we would have already known if it's heavier or lighter), we can still conclude whether each coin is problematic. Therefore, the number of coins put on the scale cannot exceed the upper limit of the second question. So, the answer to the third question is obviously 3k12\frac{3^k-1}{2}.

    Solution Construction

    We have proven the lower bound of this type of problem, and the other difficulty lies in constructing the solution.

    Here is a general method to solve the problem. The process is consistent, but if you need a more practical construction method, you can refer to the end of this post.

    Let's take the second question as an example. We use a method called "ternary numbering" to construct the solution.

    Taking 1212 coins as an example again: We know from the proof that we only need to weigh 33 times to find the problem coin. Therefore, our numbering will be 33 digits. According to the following method:

    • The first coin is numbered as 001001;
    • The second coin's number is generated by moving each digit of the first coin's number 11 place forward, i.e., 010\rightarrow1, 121\rightarrow2, 202\rightarrow0. So the number of the second coin is 112112;
    • Similarly, the third coin is 220220.

    The new numbers of these three coins form a "rotation". They meet the following characteristic: In the new numbers, when we encounter the first different digit from the left, it, and the preceding digit, together, form 0101, 1212, or 2020. We call them "normal" numbers.

    For the fourth coin, according to the new number of the first coin, we find the next ternary number. It needs to satisfy: in the new number from left to right, the first non-0 digit is 1. So, the fourth coin's number is 010010. Similarly, we continue this "rotation". The fifth coin's number is 121121, and the sixth coin's number is 202202 \dots

    As an additional feature, the conversion between ternary and decimal is as follows:

    When the original number is 3a23a-2, the new number (normal order) in ternary is: a+3log32a12a+\frac{3^{⌈\log_{3}{2a}⌉}-1}{2};

    The new number (in reverse order) and the cases when the original number is 3a13a-1, 3a3a, etc., follow the same pattern.

    Here are the normal order and reverse order of the new numbers:

    Original NumberNew Number (Normal Order)Corresponding New Number (Reverse Order, interchange 0 and 2)
    1001221
    2112110
    3220002
    4010212
    5121101
    6202020
    7011211
    8122100
    9200022
    10012210
    11120102
    12201021

    Ternary to decimal conversion:

    When the original number is 3a23a-2, the new number (normal order) in ternary is: a+3log32a12a+\frac{3^{⌈\log_{3}{2a}⌉}-1}{2};

    The new number (reverse order) and the cases when the original number is 3a13a-1, 3a3a, etc., follow the same pattern.

    The strategy for weighing is straightforward:

    • In the iith weighing, we put the coins with the iith digit of their new number being 00 or 22 on both sides of the balance scale. If the result is left heavy, we record 00; if it's right heavy, we record 22; if it's balanced, we record 11.
    • Finally, we record the results of the three weighings, which gives us the number of the problem coin. If it is in normal order, then the problem coin is heavier than normal. If it is in reverse order, then the problem coin is lighter than normal.

    This method is easily verifiable. We will give the solutions to the three sub-problems mentioned earlier.

    If the weight of the problem coin is not to be determined

    We just need to number the extra last coin with kk digits of 11. For example, for 1313 coins, the number of the last coin is 111111 and we can make 33 weighings.

    If the amount is less than 3k32\frac{3^k-3}{2}

    1. If the number of coins is a multiple of 33, we number them as described above. The method of operation with the balance scale remains the same.
    2. If the number of coins is one or two more than a multiple of 33, we add 11 to the original number of the last coin.
    • For example, if there are 1010 coins, we leave out number 1010 and number the last coin as 1111.
    • For example, if there are 1111 coins, we leave out number 1111 and number the last coin as 1212;

    It is easy to prove that after the first operation with the balance scale, the number of coins with the first digit of the new number being 00 or 22 is the same; and since at least 13\frac{1}{3} of the normal weight coins can be found after the first operation, if the operation encounters a situation where the number of coins with the iith digit being 00 or 22 is not the same, we just need to add the normal weight coins to make them the same.

    More Intuitive Construction

    We have given the complete solution to the coin weighing problem, but in practical operations, it is very cumbersome to assign ternary numbers to coins without the aid of a computer. Is there a more intuitive method?

    Yes, there is. We can dynamically construct the solution. Recalling our previous proof, we have the following conclusion:

    card(Lki)+card(Hki)3i\text{card}(L_{k-i}) + \text{card}(H_{k-i}) \leq 3^{i}

    where 1ik11\leq i\leq k-1

    The core of the problem is: After each weighing, we need to reduce the solution space to one-third of its original size.

    The method is: Take out 23\frac{2}{3} (rounding up) of the coins contained in LiL_i and HiH_i, place them on both sides of the balance scale, and add normal weight coins to make the number of coins on both sides of the scale the same. This ensures that no matter which side of the balance scale is heavier or lighter, the solution space can be reduced to one-third of its original size.

    To illustrate this method, let's take the example of 1212 coins again:

    • First step:
      • Divide the coins into two groups: 1 2 3 41\ 2\ 3\ 4 and 5 6 7 85\ 6\ 7\ 8.
        • If the balance is even, then the problem coin is among 9 10 11 129\ 10\ 11\ 12, go to step (1a)(1a).
        • If the balance is uneven, then the problem coin is among 1 2 3 41\ 2\ 3\ 4 or 5 6 7 85\ 6\ 7\ 8, go to step (1b)(1b).
    • Step (1a)(1a):
      • Put 9 109\ 10 on the left side of the balance scale, and 1 111\ 11 on the right side.
        • If the balance is even, then the problem coin is 1212, done.
        • If the balance is uneven, then the problem coin is among 9 10 119\ 10\ 11.
    • Step (1b)(1b):
      • Divide the coins into two groups: 1 2 51\ 2\ 5 and 3 4 63\ 4\ 6.
        • If the balance is even, then the problem coin is 77 or 88, go to step (2ba)(2ba).
        • If the balance is uneven, then the problem coin is among 1 21\ 2 or 5 65\ 6, go to steps (2bb)(2bb) or (2bc)(2bc).
    • Step (2aa)(2aa):
      • Put 1212 on the left side of the balance scale, and 11 on the right side.
        • If the balance is even, then the problem coin is 1111, done.
        • If the balance is uneven, then the problem coin is 99 or 1010.
    • Step (2ab)(2ab):
      • Put 99 on the left side of the balance scale, and 1010 on the right side.
        • If the balance is even, then the problem coin is 1111, done.
        • If the balance is uneven, then the problem coin is among 9 109\ 10.
    • Step (2ba)(2ba):
      • Put 77 on the left side of the balance scale, and 88 on the right side.
        • If the balance is even, then the problem coin is 77 or 88, done.
        • If the balance is uneven, then the problem coin is among 77 or 88.
    • Step (2bb)(2bb):
      • Put 11 on the left side of the balance scale, and 22 on the right side.
        • If the balance is even, then the problem coin is 11 or 22, done.
        • If the balance is uneven, then the problem coin is among 11 or 22.
    • Step (2bc)(2bc):
      • Put 33 on the left side of the balance scale, and 44 on the right side.
        • If the balance is even, then the problem coin is 33 or 44, done.
        • If the balance is uneven, then the problem coin is among 33 or 44.

    This gives us a more intuitive dynamic solution.