Solving fake coin weighting tasks

Good day to all Khabrovites .

I was looking the other day for TK to deepen programming knowledge and stumbled on one site on the problem of weighing coins to identify fake.

This problem has several varieties:
1) determine the number of weighings to identify a fake coin (it is lighter or heavier)
2) determine the weighing algorithm
3) determine the heavier or easier fake coin
and the layout of the varieties.


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

  • of 3 coins false can be determined in one weighing (it will be either one of the weighed ones, or in balance)
  • of 9 coins can be determined in 2 weighings
  • out of 27 - for 3 weighings, etc.

In total, to determine the number of weighings - n for A - the number of coins, it is necessary to fulfill the condition:
3 n > = A, or logA / log3 <= n,
where
  • A is the number of coins,
  • n - number of weighings (rounded up integer)
  • log is the decimal logarithm.

eg:
  • for 26 coins you need log26 / log3 = 2.966, n = 3 weighings
  • for 1563 coins - log1563 / log3 = 6.694 n = 7 weighings


2. Weighting Algorithm

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

1) We determine the number of weighings. As a rule, tasks set for how many weighings it is necessary to determine a fake coin, but in this way we will check whether the problem has a solution. According to paragraph 1, we obtain the number n.

logA / log3 <= n

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

if the desired 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 - we divide by sex into two groups (left group - LG, right group PG). We get three groups of

LG, PG, C.

4) Groups LG, PG - weighed and determine the group with a fake coin (D). There are 3 options:
a) the left group (LG) of coins on the scales is heavier / lighter (D = LG)
b) the right group (PG) of coins on the scales is heavier / lighter (D = PG)
c) the groups of coins on the scales are the same, then fake coin remaining (D = C).

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

6) if there are 2 coins left, perform the last weigh-in (LG = 1 and PG = 1)

7) a fake coin is found.

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

4) Weigh LG and PG.

Options after the 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) balance (C = 8) - with a fake coin . repeat steps 1-4 for 8 coins
A = 8
1) the number of weighings
log8 / log3 = 1.893
n = 2
2) we divide into groups
B = 8 - 3 (2 - 1) + 1 = 6
C = 8 - 6 = 2
3) we divide group B in half:
LH = 3, PG = 3, the remainder C = 2

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

Well, and the third weighing - from 2 or 3 coins to determine the fake, 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) LG = 8, PG = 8, C = 9
Options after the 1st weighing
a) D = LG = 8
b) D = PG = 8
c) D = C = 9
Weighing 8 coins is shown in the previous example ( Well, it coincided favorably by chance), I will show for 9.
A = 9
1) n = 2
2) B = 9 - 3 (2 - 1) = 6
C = 9 - 6 = 3
3) LG = 3, PG = 3, C = 3
and 2 more weighings (to determine groups and to determine the coin).

3. Definition of a heavier or lighter counterfeit coin

The third point of the task remained - to determine the harder the fake coin or easier.
A separate article will be devoted to this decision (well, I think that will be).

Also popular now: