Solving problems on the determination of a fake coin weighing 2.0

Today, I again want to return to the topic of the problem of finding a fake coin by weighing on scales without a dial.

The most common of these tasks is determining the number of weighings to identify a false coin if:

1) it is not known what it is by weight;
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 detect 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, I had already described the solution of such a problem at Habré, but in one of the comments there was a remark about a slightly strange first separation of coins, therefore 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 ₃ 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 from 9, for 3 from 27, etc.)

The solution algorithm itself is simple, and I will show it with examples.

1) Suppose we have 26 coins. Find one that is lighter / harder.

The first action will be the division of coins into three groups, in two of which the number of coins will be the same, it is only important that there would be 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 the number of coins divided 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,

At the first weighing two groups will be compared: right (PG) - 9 coins and left (LG) - 9 coins.

Then we have two options:

1) a fake coin in the left / right group (9 coins)
2) a fake coin in the balance (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 the 2 or 3 coins is lighter / heavier

I will give the same result in the table

Weighing number	Number of coins	LH	PG	Remainder
one	26	9	9	eight
2	eight	3	3	2
2	9	3	3	3
3	2	one	one	0
3	3	one	one	one

according to the formula - log ₃ 26 = 2.9656 - respectively, the number of weighings is 3.

another example:
the number of coins is 71. According to the formula log ₃ 71 = 3.8800 - the number of weighings is 4. We check

Weighing number	Number of coins	LH	PG	Remainder
one	71	24	24	23
2	23	eight	eight	7
2	24	eight	eight	eight
3	7	3	3	one
3	eight	3	3	2
four	2	one	one	0
four	3	one	one	one

Well, with the algorithm for solving these problems, I think, is understandable.

2. We now turn to problems in which it is not known whether a coin is lighter or heavier.

In this case, I propose this first action: to divide the coins into four groups, three - with the same number of coins as possible, and in the fourth group - the remainder. And 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 the number of coins divided by 3, a natural number, rounded down;
C is the remainder.

For example, for 58 coins it will be 58 = 3 * 19 + 1, for 23 = 3 * 7 + 2, for 15 = 3 * 5 + 0, etc.

Further we carry out 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, the second or the third group differ in weight from the other two, or they are equal, then we are lucky, because the fake one is in balance. Similarly, two weighings help to determine a heavier counterfeit coin or easier. By the way, if there are two coins in the balance, then you need to perform another 2 weighings to determine the counterfeit coin.

Now we have a task: to identify one fake coin from a group that is lighter / heavier.
As for the formula, it will take the following form

N> = log ₃ 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 consider that B = A / 3, where A is the number of all coins, then we get:

log3B = log ₃ A - 1,

N> = log ₃ 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 ₃ A

2) if it is not known which is fake, then the maximum number of weighings is determined by the formula:

N> = log ₃ A + 1

where N is the maximum required number of weighings, a natural number, rounded up;
And - the number of coins.