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:
- Given 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?
- Given 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?
- Given 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 (where denotes rounding up to the nearest integer). The answer to the second problem is , and the answer to the third problem is .
In other words, using the balance scale times, we can distinguish between , , and coins respectively.
The first problem is relatively simple. Since we know whether the problem coin is heavier or lighter, by putting approximately (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 times, we can distinguish among at most coins and determine whether the problem coin is heavier or lighter.
Let be the set of possibly lighter coins after the th weighing, and be the set of possibly heavier coins.
If we know the problem coin and its weight after weighings, then:
where denotes the number of elements in set .
Considering the th weighing, there are only three possible outcomes: left side heavier, right side heavier, or balanced. So, before the th weighing, the number of possibly problem coins can be at most , which means:
This conclusion can be recursively generalized:
where .
Therefore, after the first weighing, we have:
After the first weighing, suppose we put coins on each side of the balance scale, and coins are not on the scale, making a total of coins.
- If the scale is unbalanced, then either the heavier side or the lighter side contains the problem coin, so .
- If the scale is balanced, among the remaining coins, there is a lighter or heavier coin, so .
Thus, we have:
Considering and are both integers, we have:
Therefore:
Furthermore, we consider the third question: if we don't need to determine whether the problem coin is heavier or lighter.
In this case, and can each only contain one coin.
In this situation, it's still true that after 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 .
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 coins as an example again: We know from the proof that we only need to weigh times to find the problem coin. Therefore, our numbering will be digits. According to the following method:
- The first coin is numbered as ;
- The second coin's number is generated by moving each digit of the first coin's number place forward, i.e., , , . So the number of the second coin is ;
- Similarly, the third coin is .
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 , , or . 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 . Similarly, we continue this "rotation". The fifth coin's number is , and the sixth coin's number is
As an additional feature, the conversion between ternary and decimal is as follows:
When the original number is , the new number (normal order) in ternary is: ;
The new number (in reverse order) and the cases when the original number is , , etc., follow the same pattern.
Here are the normal order and reverse order of the new numbers:
Ternary to decimal conversion:
When the original number is , the new number (normal order) in ternary is: ;
The new number (reverse order) and the cases when the original number is , , etc., follow the same pattern.
The strategy for weighing is straightforward:
- In the th weighing, we put the coins with the th digit of their new number being or on both sides of the balance scale. If the result is left heavy, we record ; if it's right heavy, we record ; if it's balanced, we record .
- 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 digits of . For example, for coins, the number of the last coin is and we can make weighings.
If the amount is less than
- If the number of coins is a multiple of , we number them as described above. The method of operation with the balance scale remains the same.
- If the number of coins is one or two more than a multiple of , we add to the original number of the last coin.
- For example, if there are coins, we leave out number and number the last coin as .
- For example, if there are coins, we leave out number and number the last coin as ;
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 or is the same; and since at least 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 th digit being or 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:
where
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 (rounding up) of the coins contained in and , 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 coins again:
- First step:
- Divide the coins into two groups: and .
- If the balance is even, then the problem coin is among , go to step .
- If the balance is uneven, then the problem coin is among or , go to step .
- Divide the coins into two groups: and .
- Step :
- Put on the left side of the balance scale, and on the right side.
- If the balance is even, then the problem coin is , done.
- If the balance is uneven, then the problem coin is among .
- Put on the left side of the balance scale, and on the right side.
- Step :
- Divide the coins into two groups: and .
- If the balance is even, then the problem coin is or , go to step .
- If the balance is uneven, then the problem coin is among or , go to steps or .
- Divide the coins into two groups: and .
- Step :
- Put on the left side of the balance scale, and on the right side.
- If the balance is even, then the problem coin is , done.
- If the balance is uneven, then the problem coin is or .
- Put on the left side of the balance scale, and on the right side.
- Step :
- Put on the left side of the balance scale, and on the right side.
- If the balance is even, then the problem coin is , done.
- If the balance is uneven, then the problem coin is among .
- Put on the left side of the balance scale, and on the right side.
- Step :
- Put on the left side of the balance scale, and on the right side.
- If the balance is even, then the problem coin is or , done.
- If the balance is uneven, then the problem coin is among or .
- Put on the left side of the balance scale, and on the right side.
- Step :
- Put on the left side of the balance scale, and on the right side.
- If the balance is even, then the problem coin is or , done.
- If the balance is uneven, then the problem coin is among or .
- Put on the left side of the balance scale, and on the right side.
- Step :
- Put on the left side of the balance scale, and on the right side.
- If the balance is even, then the problem coin is or , done.
- If the balance is uneven, then the problem coin is among or .
- Put on the left side of the balance scale, and on the right side.
This gives us a more intuitive dynamic solution.