Geekly Articles each Day
📜 ⬆️ ⬇️

Solving problems on determining a fake coin by weighing

Good day to all habrovchanam .

I was looking for TK the other day to deepen my programming knowledge and stumbled across a single site on the task of weighing coins to detect fake.

This task has several varieties:
1) determine the number of weighings to identify a fake coin (it is lighter or heavier)
2) determine the weighting algorithm
3) the definition is heavier or easier counterfeit coin
Well, the layout of species.
')

It was possible to google, but with something she hooked me, and after several hours of nightly comprehension of the results, I managed to get the following:
1. Determine the number of weighings.


Total to determine the number of weighings - n for A - the number of coins, the condition must be met:
3 n > = A, or logA / log3 <= n,
Where

eg:


2. Weighting algorithm

Now I will show the general algorithm of weighing A coins (in order to clarify item 1) and I will use some kind of algorithmic language. Let us know that a fake coin is heavier / lighter.

1) Determine the number of weighings. As a rule, in tasks it is set for how many weighings it is necessary to determine a fake coin, but in this way we will check if the task has a solution. According to Section 1, we get the number n.

logA / log3 <= n

2) Next, divide the coins into 2 groups as follows

if the number is odd
B = A - 3 (n - 1)

if the desired number is even
B = A - 3 (n - 1) + 1

and the second group

C = A - B

3) Group B - divide by sex into two groups (left group - LH, right group PG). We will have three groups.

LH, PG, C.

4) Groups of LH, PG - we weigh and determine the group with a false coin (D). There are 3 options:
a) the left group (LH) of coins on the scales is heavier / lighter (D = LH)
b) the right group (PG) of coins on a heavier / lighter scale (D = PG)
c) the groups of coins on the scales are the same, then the fake coin in the balance (D = C).

5) For the group found in step 4, repeat paragraphs 1-4 (A = D), while the number of coins is greater than 2 (A> 2)

6) if 2 coins are left, we perform the last weighing (LG = 1 and PG = 1)

7) fake coin found.

Consider for clarity the task, let it be from the same site: you need to divide 12 coins in 3 weighings, a fake coin is easier.
1) the number of weighings
log12 / log3 = 2.261
n = 3 (well, the problem has a solution)
2) divide into groups
B = 12 - 3 (3 - 1) + 1 = 4
C = 12 - 4 = 8
3) group B is divided in half:
LH = 2, PG = 2, residue C = 8

4) Weigh LH and PG.

Options after 1st weighing
a) LG = 2 - with a fake coin (go to step 6)
b) PG = 2 - with a fake coin (go to step 6)
c) the balance (C = 8) - with a fake coin. repeat the PP.1-4 for 8 coins
A = 8
1) the number of weighings
log8 / log3 = 1.893
n = 2
2) divide into groups
B = 8 - 3 (2 - 1) + 1 = 6
C = 8 - 6 = 2
3) group B is divided in half:
LH = 3, PG = 3, residue C = 2

Options after the 2nd weighing
a) LG = 3 - with a fake coin (repeat paragraphs 1-4 for 3 coins A = 3)
b) PG = 3 - with a fake coin (repeat paragraphs 1-4 for 3 coins A = 3)
c) the balance (C = 2) - with a fake coin. go to paragraph 6)

Well, the 3rd weighing - from 2 or 3 coins to determine the false one, and for 3 coins the rule will also work.

Another example for 25 coins
1) n = 2.93 = 3
2) B = 25 - 3 (3 - 1) = 16
C = 25 - 16 = 9
3) LH = 8, PG = 8, C = 9
Options after 1st weighing
a) D = LH = 8
b) D = PG = 8
c) D = C = 9
Weighing 8 coins is shown in the previous example (well, it so coincidentally favorably matched), I will show for 9.
A = 9
1) n = 2
2) B = 9 - 3 (2 - 1) = 6
C = 9 - 6 = 3
3) LH = 3, PG = 3, C = 3
well, and 2 more weighing (to determine the group and to determine the coin).

3. Definition of heavier or lighter counterfeit coin.

The third point of the task remains - to determine the heavier the counterfeit coin or easier.
A separate article will be devoted to this decision (well, I think it will be so).

Source: https://habr.com/ru/post/169771/

More articles:


All Articles