Problem solving for determining a fake coin by weighing 2.0
Today I again want to return to the topic of the problem of finding a fake coin by weighing on a scale without a dial.
The most common of these tasks is determining the number of weighings to identify a fake coin, if:
1) it is not known what weight it is;
2) it is known that it is lighter / heavier than the rest.
Or the inverse problem: is it possible for a certain number of weighings to identify a fake of a given number of coins.
1. Let's first deal with option 2, which is a special case of option 1.
Some time ago, on Habré I already described the solution to such a problem , but in one of the comments there was a comment about a bit strange first separation of coins, that's why I propose a different solution algorithm. Although the result will be the same and the formula for solving the problem remains the same:
N> = log 3 A,
where N is the maximum required number of weighings, a natural number, rounded up;
A is the number of coins.
Which is derived on the basis of experiments (for 1 weighing you can find one fake of 3 coins, for 2 - of 9, for 3 - of 27, etc.)
The solution algorithm itself is simple, and I will show it in examples
1) Let we have 26 coins. You need to find one that is easier / heavier.
The first step is to split the coins into three groups, in two of which the number of coins will be the same, it’s important that there are fewer coins in the third group — the remainder — than in each of the other two groups. That is, the frequent is rounded to a larger natural number. I.e
A = 2 * B + C,
where A is the number of coins;
B - quotient of dividing the number of coins by 3, a natural number, rounded up;
C is the remainder.
By the condition of the problem,
26/3 = 8.666 (6),
26 = 2 * 9 + 8.
During the first weigh-in, two groups will be compared: the right (PG) - 9 coins and the left (LG) - 9 coins.
Further, we have two options:
1) a fake coin in the left / right group (9 coins)
2) a fake coin in the remainder (8 coins)
for option 1, the next division into groups will be - 9 = 2 * 3 + 3;
for 2 options - 8 = 2 * 3 + 2
Well, for one weighing, you can determine which of 2 or 3 coins is lighter / heavier
. I will give the same result in the table
| Weighing number | Number of coins | Lh | PG | The remainder |
| 1 | 26 | 9 | 9 | 8 |
| 2 | 8 | 3 | 3 | 2 |
| 2 | 9 | 3 | 3 | 3 |
| 3 | 2 | 1 | 1 | 0 |
| 3 | 3 | 1 | 1 | 1 |
according to the formula - log 3 26 = 2.9656 - respectively, the number of weighings - 3.
another example: the
number of coins - 71. According to the formula log 3 71 = 3.8800 - the number of weighings - 4. Check
| Weighing number | Number of coins | Lh | PG | The remainder |
| 1 | 71 | 24 | 24 | 23 |
| 2 | 23 | 8 | 8 | 7 |
| 2 | 24 | 8 | 8 | 8 |
| 3 | 7 | 3 | 3 | 1 |
| 3 | 8 | 3 | 3 | 2 |
| 4 | 2 | 1 | 1 | 0 |
| 4 | 3 | 1 | 1 | 1 |
Well, with an algorithm for solving these problems, I think, is understandable.
2. Now we turn to tasks in which the coin is not known lighter or heavier.
In this case, I propose this first action: divide the coins into four groups, three with the most equal number of coins, and the remainder in the fourth group. Moreover, the balance should be 1 or 2 coins. That is, when divided by 3, the quotient is rounded to a smaller natural number.
A = 3 * B + C,
where A is the number of coins;
B is the quotient of dividing the number of coins by 3, a natural number, rounded down;
C is the remainder.
For example, for 58 coins - this will be 58 = 3 * 19 + 1, for 23 = 3 * 7 + 2, for 15 = 3 * 5 + 0, etc.
Next, we perform two weighings:
1) the first and second groups
2) the first and third groups;
and analyze the result.
Four options are possible here: 1, 2, 3 - this is the first, second or third group differ in weight from the other two, or they are equal, then we were lucky, since the fake is the remainder. Also, two weighings help determine whether it is harder to fake a coin or easier. By the way, if there are two coins in the balance, then you need to do 2 more weighings to determine a fake coin.
Now we have a task: to identify one counterfeit coin from a group that is lighter / heavier.
As for the formula, it will take the following form
N> = log 3 B + 2,
where N is the maximum required number of weighings, a natural number;
B - the number of coins in the group after the second weighing.
And if we take into account that B = A / 3, where A is the number of all coins, then we get:
log3B = log 3 A - 1,
N> = log 3 A + 1
Total:
1) if it is known that a fake coin is lighter / heavier, then the maximum number of weighings is determined by the formula:
N> = log 3 A
2) if it is not known which is false, then the maximum number of weighings is determined by the formula:
N> = log 3 A + 1
where N is the maximum required number of weighings, a natural number, rounded up;
A is the number of coins.