11
$\begingroup$

You need to find two fake coins from a pile of 30 coins. You know that a fake coin has a different weight to a real coin, but you don't know whether it is lighter or heavier. You also know that all real coins weigh the same and all fake coins weigh the same. What is the least number of weightings you need to make to find the two fake coins using a two-sided scale? You can place any number of coins on each pan and each weighting has three outcomes: tip to left, stay equal, tip to right.

This puzzle was inspired by these great puzzles:

30 fake coins out of 99 coins

Twelve balls on a scale, where one ball is lighter and another is heavier

$\endgroup$

5 Answers 5

4
$\begingroup$

There are ${30 \choose 2} = 435$ ways of selecting 2 coins out of 30. Since the fakes can be heavy or light, that yields $435 \times 2 = 870$ possible combinations.

Since each test yeilds one of 3 outcomes, and $3^6 = 729 < 870 < 2187 = 3^7$, at least 7 tests are needed.

Below is proof that

7 tests will always work.

This would be easier if we had only $27$ coins, as ${27 \choose 2}\times 2 = 702 < 729$, so we could complete the task in 6 tests.

To solve 27 coins, make a $3 \times 3 \times 3$ cube, and put one coin in each cell. Then weigh the top layer versus bottom layer, near layer versus far layer, and left layer versus right layer.

No matter what the outcome of the 3 tests, there will remain 13 possible combinations of heavy fakes and 13 possible combinations of light fakes (the combinations may not be the same).

For example, if all three tests came out level, then each cell pairs with its direct opposite, except the middle cell, which would pair with itself. This is the same whether the fakes are heavy or light.

If the results were top > bottom, left > right, and near > far, then the heavy combinations are (using $tln$ to signify top-left-near, and $m$ for middle):

$(tln,mmm), (tln,tmm), (tln,mlm), (tln,mmn), (tln,tlm),$ $(tln,tmn), (tln,mln), (tlm,mmn), (tlm,mln), (tlm,tmn),$ $(tmn,mln),(tmn,mlm),(tmm,mln)$

The 13 combinations if the fake coins are light are the opposite combinations to these.

At this point, you would have 13 possible combinations for light, 13 for heavy, and one known genuine coin. There is a standard solution for the problem of 13 coins including one fake plus one known genuine coin. This can be solved in 3 tests. In this case, it's slightly tricky as the combinations are different if the fakes are heavy versus light.

But we don't have 27 coins, we have 30. So, to try something similar: make the same cube, put one coin in each cell, then add three more coins: pick two opposite corners and put an extra coin in each cell and the last coin in the middle cell. Then proceed as above to identify a combination of cells that contain the fake coins. Given the symmetry of coin placement, each test will weigh 10 coins against 10 coins.

Note that it is possible for a 14th combination to appear, as a cell can now match itself. For example, if all the tests balance, then it could be the two coins in the middle cell that are the fakes. This means that there can be up to 17 combinations for each of heavy-light after the first 3 tests, for a net of 34 options.

For example, if all tests balance, then the fakes are either in two cells that are opposite one another, as above, or both in the middle cell. Since two of the corner cells have 2 coins each, that cell-pair has four coin-pairs, instead of the usual 1. These additional 3, plus the 1 for the middle cell, lead to a total of 17 pairs. And since we do not yet know if the fakes are heavy or light, that yields 34 combinations to sort through.

So now the problem is how to solve the 34 possible remaining combinations with 4 weighings. It's impossible to do in 3, as $34 > 27 = 3^3$. But since 34 is far less than $81 = 3^4$ it should be straightforward to solve the puzzle.

Update with more details

If all the first three tests balance, then the fakes are in opposite cells in the cube or both in the middle. If you number the cells using a standard grid, 1-27, number each coin and put it in that cell, then add coin 28 to cell 1, 29 to cell 14, and 30 to cell 27, then the combinations are:

(1,27), (2,26), (3,25), ..., (13, 15), &
(1,30), (28, 27), (28, 30), and (14,29).

For test 4, weigh (1,2,3,4,28) vs (5,6,7,8,9).

Test 4 balances: No combination includes any 2 of the coins used in test 4, so if the scale balances, it means neither fake is in that set. Thus, one of 10, 11, 12, 13, or 14 is fake, and all the coins weighed (and their counterparts) are genuine. Use the standard solution for 12 or fewer coins containing a fake to determine which of these 5 coins is fake and whether heavy or light. This takes 3 more tests. Once a fake is determined, the other fake is the partner listed above.

Test 4 tilts left, in this case, either (1, 2, 3, 4, 28) contains a heavy fake or (5, 6, 7, 8, 9) contains a light fake. In addition, if either 1 or 28 is fake, then the other fake is either 27 or 30. This yields 12 possible combinations.

For test 5, weigh (1,2,5,6) vs (3,4,7,8).

Test 5 Balances: Either 28 or 9 is fake. Test 6: weigh 27 vs 30, yielding (9,19) if it balances or (27,28) if it tilts left or (27,30) if it tilts right.

Test 5 tilts left: One of (1,2,7,8) is fake, for 5 options (since 1 can pair with 27 or 30). Test 6: weigh 7 vs 8 and if they balance, then Test 7: 27 vs 30. If 7 & 8 balance and 27 & 30 balance, then (2,26) are the fakes.

Test 5 tilts right: One of (3,4,5,6) is the fake. Weigh 3 vs 4, then 5 vs 6 to determine the fakes.

Test 4 tilts right: This is the same as for the "tilts left" case, but with heavy and light reversed.

Similar strategies work for the cases where 1, 2, or all three of the first three tests balanced.

$\endgroup$
4
$\begingroup$

These steps detail a full algorithm to figuring out which two coins are fake. Worst case, this takes $10$ comparisons.

Edit: The algorithm was fixed to account for the error noted in the comments. This didn't affect the worst case scenario.

Step 1: Split the $30$ coins into $3$ piles of $10$, which we will call $A$, $B$, and $C$. Compare $A$ and $B$. If they weigh the same, move to step $2$, else move to step $14$.

Step 2: We know that either $A$, $B$ both have a fake coin and $C$ has no fake coins, or that $C$ has two fake coins and $A$, $B$ have neither. So, split $A$ into two piles of $5$ and compare. If the piles weigh the same, move to step $3$, else move to step $17$.

Step 3: We know that both fake coins are in a pile of $10$ coins, so split this pile into two piles of $5$, which we label $C_1$ and $C_2$. If they weigh the same, move to step $4$, else move to step $8$.

Step 4: We know both $C_1$ and $C_2$ have a fake coin. Take $2$ coins from $C_1$ and weigh against $2$ coins from $B$. If they weigh the same, move to step $5$, else move to step $6$.

Step 5: We know that the fake coin is one of $3$ coins in $X$ that weren't measured in step $4$. Take two of these coins and weigh them against each other. If they are different, move to step $6$, else we know that the unmeasured coin is the fake coin. Move to step $4$, but instead of $C_1$, apply the steps to $C_2$. Finish at step $5$ or $6$.

Step 6: We know that the fake coin is one of $2$ coins, so we weigh one of these coins against a coin from $B$. If it is the same, the unweighed coin is fake, otherwise the weighed coin is fake. After this step, we also know whether the fake coin is lighter or heavier than the normal coin. Move to step $7$.

Step 7: Split $C_2$ into piles of $2$, $2$, and $1$. Weigh the two piles of two against each other. If they are the same, we know that the unmeasured coin is the fake one. If they are different, depending on which pile is heavier, we know which pile contains the fake coin. Move to step $6$ and finish there.

Step 8: We know one of the piles of $5$ contains two fake coins, so weigh one of these piles against a pile of $5$ from $B$. If they are the same, move to step $9$, otherwise, move to step $13$.

Step 9: We know that the unweighed pile of $5$ has $2$ fakes. Split the pile into $2$, $2$, and $1$, and weigh the piles of $2$ against each other. If they are the same, move to step $10$, else move to step $11$.

Step 10:: We know both piles of $2$ have one fake coin. For each pile, weigh one coin against a coin from $B$. If they are the same, the unmeasured coin is fake, otherwise the measured coin is fake.

Step 11: We know that one of the piles has no fakes, and one pile has either one fake coin (and the unmeasured coin is also fake) or has two fake coins. Take one of the piles of $2$ and measure it against a pile of $2$ from $B$. We now know whether the fake coins are lighter or heavier than the normal coin, and which pile of $2$ contains at least one fake. Move to step $12$

Step 12: Measure the two coins from the pile with at least one fake against each other. If they are the same, then they both are fake. Otherwise, the unmeasured coin is fake, as is the coin that coincides with whether the fake is lighter/heavier than the normal coin.

Step 13: We know that the weighed pile of $5$ has $2$ fakes, so split it into piles of $2$, $2$, and $1$, and weigh the piles of $2$ against each other. If they weigh the same, move to step $10$, else move to step $12$ (we know whether the fake is lighter/heavier than the normal coin already, so we know which pile has at least one fake).

Step 14: We know that either $A$ or $B$ has two fakes, or that one of them has $1$ fake and $C$ has one fake. Split $C$ into piles of $5$ and compare them. If they are the same, move to step $15$. Else, move to step $22$.

Step 15: We know that either $A$ or $B$ has $2$ fakes. Compare $A$ with $C$. Regardless of result, we will have a pile of $10$ coins with $2$ fakes, and we will know whether the fake coins are lighter or heavier than the normal coins. Rename $C$ to $B$. Move to step $16$.

Step 16: Split the pile of $10$ into $2$ $5$ coin piles called $C_1$, $C_2$. Compare them. If they are the same, move to step $4$. Else, we know that we have a pile of $5$ coins with $2$ fakes. Move to step $13$.

Step 17: We now have two piles of $10$, each with one fake, and one pile of $10$ with no fakes. Call the piles with fakes $A,\;C$, and the pile without a fake $B$. From the previous step, we also have $2$ sub-piles of $A$ of size $5$, which we will call $A_1$, $A_2$, such that $A_1$ is lighter than $A_2$. Compare $A_1$ with $5$ coins from $B$. Regardless of result, move to step $18$.

Step 18: We now know which sub-pile of $A$ contains a fake, and whether the fake is lighter or heavier than a normal coin. Split this sub-pile into groups of $2$, $2$, and $1$, and weigh the groups of $2$ against each other. If they are equal, we know that the unmeasured coin is the fake one in $A$. Otherwise, measure the two coins from the group with the fake coin against each other to figure out which coin is fake. Move to step $19$.

Step 19: We now focus on $C$. Split $C$ into groups of $3$, $3$, and $4$, and compare the groups of $3$. If they are equal, move to step $20$. Else, move to step $21$.

Step 20: We know that the fake coin is in the group of $4$. Take two coins from this group and compare. If they are unequal, we know which coin in $C$ is fake. If they are equal, compare the two remaining coins to see which coin is fake.

Step 21: We know which group of $3$ the fake coin is in. Take two coins from the group and compare them. If they are equal, the unmeasured coin is fake. If not, we know which of the two is fake.

Step 22: Split $A$ into two piles, and compare. This tells us whether $A$ or $B$ has the fake. Move to step $17$.

$\endgroup$
2
  • 2
    $\begingroup$ I haven't reviewed your solution thoroughly, but I did find a mistake in step 17. To get to this point you compared A with B, which were uneven, and C1 with C2 which were also uneven. Then you state "call the pile without a fake B", however, since at this point you don't know if the fake coins are light or heavy, there is no way to know which pile does not have a fake. It only takes 1 more weighing to figure it out, I don't know how that factors into your minimum worst case comparisons. $\endgroup$
    – Amorydai
    Nov 4, 2019 at 4:47
  • 2
    $\begingroup$ @Amorydai Thank you for reading through! That's definitely an error, I kinda got swamped in the case work, and messed that up. I'll update that when I get time, and recalculate the worst case. $\endgroup$ Nov 4, 2019 at 4:53
1
$\begingroup$

I have an algorithm to achieve the task with no more than

7 weighings.

There are some interesting solutions here, most of them do not appear to be complete, however, so I have decided to add mine as well.

First, divide the 30 coins into 5 groups of 6 coins each. Label them A, B, C, D, and E. The gist of the algorithm is to find out which of these groups have a fake and then find the fake. Here are the steps:

Step 1: Compare A and B to C and D. (1 weighing)

If equal go to step 2. (Either 1 fake in AB and 1 fake in CD or 2 fakes in E)
If not equal go to step 4. (Either 2 fakes in AB or CD or 1 fake in AB or CD and 1 in E)

Step 2: Compare A to B. (1 weighing)

If equal there are 2 fakes in E. Compare A to E to determine if fakes are light or heavy (1 weighing). Go to CASE 2F (3 weighings). You have found the two fakes. 3 plus 3 weighings already made for a total of 6.
If not equal go to step 3. (1 fake in AB and 1 fake in CD)

Step 3: There is 1 fake in CD. Got o CASE 12C (3 weighings). You have found a fake coin and if it is heavy or light. From step 2 you now know if the second fake is in A or B. Take that group and go to CASE 1F (2 weighings). You found the two fakes. 1 + 1 + 3 + 2 = 7 total weighings.

Step 4: Compare A and C to B and D. (1 weighing)

If equal there is now 1 fake on each side of the scale. Take BD and go to CASE 12C (3 weighings). You now have 1 fake and know if it’s light or heavy. From step 1 you know if the second fake is in A or C. Go to CASE 1F (2 weighings). You have 2 fake coins. 1 + 1 + 3 + 2 = 7 total weighings.

If not equal:
If the heavy side of the scale did not change fakes are in A or D and maybe E. Good coins are in C and B. Label good coins G1 and G2. If A was on the heavy side label it FH and label D FL. Otherwise label A FL and D FH. Go to step 5.
If the scale changed sides the fakes are in B or C and maybe E. Good coins are in A and D. Label good coins G1 and G2. If B was on the heavy side label it FH and C FL, otherwise label C FH and B FL. Go to step 5.

Step 5: Compare G1 and E. (1 weighing)

If equal then 2 fakes are in either FH or FL. Go to step 6.
If not equal there is 1 fake in E and you know if it’s light or heavy. Using this information now you know if the second fake is in FH or FL. Take E and go to CASE 1F (2 weighings) then take FH or FL and go to CASE 1F (2 weighings). You now have two fakes. 1 + 1 + 1 + 2 + 2 = 7 total weighings.

Step 6: Compare G1 to FH. (1 weighings)

If equal the fakes are in FL. Go to CASE 2F (3 weighings). 1 + 1 + 1 + 1 + 3 = 7 total weighings.
If not equal the fakes are in FH. Go to CASE 2F (3 weighings). 1 + 1 + 1 + 1 + 3 = 7 total weighings.

CASE 1F: You have 6 coins with 1 fake and you know if the fake is light or heavy.

Step a: Compare 123 and 456. The scales will tip to show where the fake is. (1 weighing)

Step b: Compare two coins from the side with the fake. Let’s say it was 123. Compare 1 and 2. If equal the fake is 3. Otherwise the scale will show where the fake is. (1 weighing)

2 total weighings.

CASE 2F: You have 6 coins with 2 fakes and you know if the fake is light or heavy.

Step a: Compare 123 with 456. (1 weighing)

If equal go to step b.
If not equal, the scale will show the side with the fake. Let’s say it’s 123. Go to step c.

Step b: Compare 1 and 2. If equal the fake is 3, otherwise the scale will show the fake. Then Compare 4 and 5. If equal the fake is 6, otherwise the scale will show the fake. (2 weighings)

Step c: Compare 1 and 2. If equal the fakes are 1 and 2. If not equal the fakes are 3 and whichever one the scale shows. (1 weighing)

3 total weighings.

CASE 12C: You have 12 coins with 1 fake and you don’t know if it’s light or heavy.

Step a: compare 1234 and 5678. (1 weighing)

If equal go to step b.
If not equal, assume the heavy side is 1234. Go to step c.

Step b: The fake is in 9,10,11,12. Compare 1,2,3 with 9,10,11. (1 weighing)

If equal the fake is 12. Compare 1 to 12 to find out if it’s heavy or light. (1 weighing). 3 total weighings.
If not equal you have figured out if it’s heavy or light. Compare 9 to 10. If equal the fake is 11, otherwise the scale will show if it’s 9 or 10. (1 weighing). 3 total weighings

Step c: Compare 1,2,5 with 3,4,6. (1 weighing)

If equal the fake is 7 or 8. Compare 7 with 8. (1 weighing). 3 total weighings.
If 125 is heavy go to step d. (fake is either heavy 1 2 or light 6)
If 346 is heavy go to step e. (fake is either heavy 3 4 or light 5).

Step d: Compare 1 and 2. If equal then fake is 6, otherwise fake is whichever is heavy. (1 weighing). 3 total weighings.

Step e: Compare 3 and 4. If equal then fake is 5, otherwise fake is whichever is heavy. (1 weighing). 3 total weighings.

$\endgroup$
1
  • 1
    $\begingroup$ This is complete if we combine this with my part (which explains the part "not less then seven".) for 30 coins. It would be interesting to examine if 7 measurements were enough to identify 2 coins in a pile of 47 coins. (That would mean that the information theory lower bound is achievable). $\endgroup$
    – balazs.com
    Nov 8, 2019 at 12:07
1
$\begingroup$

Here is my simple methodology;

Let's call

fake as $F$, genuine as $G$ and if stay equal ($E$) if not equal ($NE$);

then

Step 12v34

Weigh two coins against two coins

and the possible outcomes become;

12 34 Result
I GG GF NE
II GG FF NE
III GG GG E
IV GF GF E

Step NE-4 (I and II)

Let's find at least one fake coin if this happens with an $NE$ condition; let's call first two coins as 1,2 and the other two coins as 3,4. At first we weighed 12 against 34, now weight 13 against 24;

1- If the result is E, we have two fake coins on one side, we have to weigh 12 against other two G coins to find two fake coins (since we do not know if fake ones are lighter or heavier), if there is E, 34 is FF, otherwise 12 is FF (total 2 tries for Step NE-4 to find two fake coins)

2- If the result is EQ, we have one fake coin and if the balance condition does not change from the step before Step NE-4, that means our fake coin is 1 or 4 (2 and 3 are G coins for sure), otherwise, if balance condition changes from left to right (or right to left doesn't matter), our fake coin is 2 or 3 (1 and 4 are G for sure). So just weigh 1 against 2 to find which coin is fake. (totally it takes 2 tries for Step NE-4 to find one fake coin if we don't know our fake coin is lighter or heavier) But this would take one less try if we had known that our fake coin was lighter or heavier. because after switching 1 and 3, we would know which coin was fake with the balance result by knowing our fake coin is lighter or heavier. (totally it takes 1 try for Step NE-4 if we had known that our fake coin was lighter or heavier.)


Step E-4

From here, I will go with $E$;

If there is E, then we need to take another 4 of them and weight against each other, if there is E again, that means all 8 of them are actually G and we have 22 coins left to check! after only two tries!

from Step 2-2 New 4 Result
I GGGG GGGG E

otherwise

if there is NE, the first 4 coins consists of the two F coins as shown above table or new 4 coins we chose consist at least one fake coin. (such as GGGF or GGFF) After two tries, we found at least one fake coin within 8 coins with some information already!

Let's put all possibilities on the table again;

From Step 12v34 New 4 Result
I GF|GF GGGG NE
II GG|GG GGFF NE
III GG|GG GGGF NE

and now, what?

of course we have other coins to compare with those; let's add another 4 coins to compare our original 1234 as below and add to the table and 4 possible outcomes we get;

From Step 2-2 New 4 Result 1 Another New 4 Result 2
I GF|GF GGGG NE GGGG NE
II GG|GG GGFF NE GGGG E
III GG|GG GGGF NE GGGG E
III-2 GG|GG GGGF NE GGGF NE

now,

we get new NE result such on the tables, we know that all of our Fake coins from Step 2-2 (I) or from Another New-4 (III-2), which is not the worst case scenario since we got all fakes ones in 8 possible coins! Moreover, if the result 1 is NE and result 2 is EE, we know that at least one fake coin is in New 4. but we tried in total 3 times to get this information for 12 coins. Moreover we also know whether if our fake coin is lighter or heavier either!

From here, if our fake coin is in New 4, we just need to split it into 2 and weigh against two coins to each other. if they are equal, it is GG|FF condition, just weight another any two pairs with some other GG, it would be 5 times in total to find two fake coins. If they are not equal, we know that we have only one fake coin, (we also know whether if it is lighter or heavier too). so wherever the fake coin is, weigh 1v1 and find our fake coin out of it. In total 5 times would be enough to find 1 fake coin out of 12 coins.


So in all conditions, we have found at least one fake coin, which is the worst case scenario. otherwise we would have found all fake coins in 5 tries at most as explained above. Now we know whether if our fake coin is lighter or heavier and we know which coin is fake in the worst case scenario. Other than that, if Step E-4 happened with another E, we would have eliminated 8 coins anyway. So two ways to go! I will leave Step E-4 with another E for now; now we have one fake coin with 18 coins left with another fake inside!

Let's divide these 18 coins into three; and weigh against each other for two couples, if they are equal, the last fake coin is in 6 coins which you did not weigh, otherwise it will be in one of these 6-coin group; so we eliminated another 12 coins in an instant. We are left with 6 coins with a fake one! Same methodology, divide 6 coins into three again and.... bla bla... get 2 left! then weigh against each other and find our last fake coin for sure! In total 7 tries.

What happened if Step E-4 with another E happened? I mean what if we get all G coins for sure? we are left 22 coins but we know our 8 other coins are G for sure. Then we would have weight these 8 coins with another 8 coins! If they are equal, we are left with 14 coins with 2 fakes without any knowledge, otherwise we know that our one fake coin is in these new 8 coins and whether if it is lighter or heavier. (3 times now)

To be continued... Too long...

$\endgroup$
1
  • $\begingroup$ An interesting approach, however, you seem to be miscounting your tries throughout the solution. It's not a big deal, except for the final conclusion where you state that you have found 1 fake coin in 5 tries, and then you have 1 more to find in 18 other coins. You cannot do that with any less than 3 tries, so for that particular scenario your solution produces at least "8" tries, not "7" as stated. Of course, the solution isn't complete for the other scenarios, so 8 might not be the lowest number achieved. $\endgroup$
    – Amorydai
    Nov 8, 2019 at 1:28
-2
$\begingroup$

At first sight I would say it is:

9

reasoning:

I think there is no point placing less than 12-12 each side for the first measurement since we can identify (not only choose the fake item but tell if weighs more or less) the fake item with n weighings if we have ((3^n-1)/2)-1 or less pieces (See mathworld.wolfram weighing and balance puzzle wikipedia references and we also know this from the classical 12 ball problem.) So the first measurement would be set I against set II each containing twelve. If there is balance, the second measurement would be 6 against 6 all from the first set. This is necessary to get know if there are 1-1 fake items in set I and II or there are 2 fake items in the remaining set (set III).After this from the 3rd measurement on we will examine either set I and set II or only set III. IF there was no balance (meaning both fake items are in set I and II) 3rd-5th and 6th-8th measurement will identify the fake items as per the method in the 12 ball problem. In different case we examine set III (let they be a,b,c,d,e,f) if 3rd measurement abc?def is balance then 4th measurement a?b, if balance then after 5th measurement c?x (x any known usual weight item) will identify, two similar measurements for the other side follow, making up 7 measurements altogether.If 4th measurement a?b inbalance then 5th measurement a or b versus x will identify and similarly plus two for the other side. IF 3rd measurement abc?def is inbalance then 4th: a?b in case of balance then 5th measurement d?e will identify and plus 2 weighings for the other side which is again summa 7. If a?b inbalance then we were looking for the heavier one and c. There is a case left when at the beginnning there would be inbalance between Set I and Set II. This is more complicated. In this case the same 2nd measurement (Set I items 6 against 6) will lead to two version (let they be X if inbalance and Y if balance). X leads to two ways. Path A: Set I subset 6 items contains one fake with known direction of altered weight AND Set III 6 items contains one fake item with known direction of altered weight. This case (using the same reference n measurements for 3^n number of items) we need an additional 4 measurements to identify all the fakes. Is is 6 measurements altogether. Path B there are two heavier but we need only examine the subset of 6 items in Set I. We already saw how to do this thorugh an example above, it will require 5 measurements, but if we start on the Path B it is possible after 3 measurements (if there are equalities) that we realize that the case is actually Path A and jump over to Path A and here we need 2-2 additional measurements (for 6 items choosing the altered one in known direction and doing this twice) it will be 8 altogether. In Case Y Path A: one item in six altered in known direction, and one item in six altered in known direction require 4 measurements, but it is possible to jump to path B after only one measurement is done (resulted and equality).Path B: either one altered in set III and one altered in Set II. Or two altered in Set II. All of them we already know if heavier or lighter. The first option will result an additional 4 measurements, meaning 7 altogether, but if the second option is the real case after one measurement we can choose the second option, so essentially by finishing the 4th measurement we will still need to examine Set II (12 items) looking for two fake items. Most likely this pathway is the most unfortunate, and will result in 9 or 10 measurements. I am two tired, continue tomorrow:)

EDIT

Not because I think the above written is entirely bullshit, but I have an intuition, that it is very arbitrary and it is far from the optimality (both in theoretical and practical terms). I have a different idea.

With this type of scale after k measurements we have 3^k outcomes. If there would be one fake coin(A) known to be heavier or lighter than the others, not more than N (such N<=3^k) coins could be examined by this method using k measurements, because the final result will have to point exactly to the fake coin, and we cannot have less information then N. In this case 30 coins could theoretically be examined with at least 4 measurements. We have two differences in this puzzle. We have two fake coins, and "fake" (B) means that we do not know whether they weigh more or less, we have to find them both and identify their weight. In case of two fakes (A) we need that (N 2)<= 3^k if n is 30 it is 435<= 3^k.This is because now we have to identify a coin-pair instead of one coin eventually. This means that at least 6 measurements would be needed. But we have two fake coins of the B type. At least one of the weighings we should see inequality, otherwise we would not be able to find out if the fake coin is heavier or lighter,so there are 3k-1 possible results of weighings. Also, the the number of possible answers is double of N (which is 30) (we have to point at one of the 30 coins and find out if it is heavier or lighter). Therefore it is necessary that (N 2)<= (3^k-1)/2 from this relation we get that k should be at least

7

There is problem with this number however. This is a calculated theoretic limit for k, or in other words a limit for n as a maximum number of coins that can be examined by k measurements. The practical proof (the weighing algorithm) is missing. It has been already examined by others that in case of two fake coins with known weights (here: type A fake coins) the theoretical limits up to 6 measurements can be reached in reality as well. (Khovanova: Coins and logic, 2018) IF such correlation existed in our case of Fake (B) coins, maybe the answer that at least 7 measurements are needed could possibly be correct.

$\endgroup$
1
  • 5
    $\begingroup$ Honestly, I have no idea as to what this says. $\endgroup$ Nov 3, 2019 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.