Jump to content
BrainDen.com - Brain Teasers
  • 0


Prime
 Share

Question

After seeing so many variations of the counterfeit coin weighing problem on this forum, I am compelled to take that puzzle to the top and slightly over. Here is my own variation:

There are 39 coins, one of them counterfeit and weighs either more, or less than a true coin.

In 4 weighings, or less on a balance-type scale, find the counterfeit and determine whether it weighs more or less than a true coin.

And for an encore… When you have solved the above problem (or not), find the only counterfeit coin (which weighs more or less) out of 40 coins with 4 weighings, or less.

Link to comment
Share on other sites

17 answers to this question

Recommended Posts

  • 0

Again, the trick with these problems is reducing the # of cases with each weighing. We have 4 weighings, so we can tell 3^4=81 cases apart. Luckily, we only have 39 coins (78 cases).

So...I did the 39 coins one. Don't want to write a huge post, but basically, it works if you move 9 coins from each set to the next after a first unbalanced weighing.

So if you call 3 sets of 13: X, Y,Z

After finding Y vs Z is unbalanced, move 9 coins from Z to Y, Y to X, and X to Z.

That way the number of possible cases after two wieghings stays below 9 since you only have two weighings left and 3^2=9.

I know this short, but this is the only trick that differentiates it from 12 coin one.

I'll post a longer answer if not clear.

The 40 I haven't tried, but 80<81 cases that we can detect. So there's bound to be an answer.

Link to comment
Share on other sites

  • 0
Again, the trick with these problems is reducing the # of cases with each weighing. We have 4 weighings, so we can tell 3^4=81 cases apart. Luckily, we only have 39 coins (78 cases).

So...I did the 39 coins one. Don't want to write a huge post, but basically, it works if you move 9 coins from each set to the next after a first unbalanced weighing.

So if you call 3 sets of 13: X, Y,Z

After finding Y vs Z is unbalanced, move 9 coins from Z to Y, Y to X, and X to Z.

That way the number of possible cases after two wieghings stays below 9 since you only have two weighings left and 3^2=9.

I know this short, but this is the only trick that differentiates it from 12 coin one.

I'll post a longer answer if not clear.

The 40 I haven't tried, but 80<81 cases that we can detect. So there's bound to be an answer.

I don't think you have the answer. The description of your method is incomplete. Also, I think you are mistaking about 78 cases. I did ask to find the counterfeit coin and whether it is lighter or heavier. That makes it 117 cases for 39 coins, as I see it. Thanks for trying.

Edited by Prime
Link to comment
Share on other sites

  • 0

Or, perhaps, there are 78 cases for 39 coins. There are 39 distinct possibilities for which coin is a counterfeit and there are two possibilities for each -- heavy or light. But I don't see that as a guarantee that you can arrange your 4 weighings in a way to determine the counterfeit. Furthermore, I see a variation of the problem, where you can not find such an arrangement.

Edited by Prime
Link to comment
Share on other sites

  • 0

divide the 39 coins into groups of 13 coins each: A, B, and C

first, compare group A with B

-if the scale tips then the counterfeit is in group A or B.

-if not then it is in group C.

second, compare A with C.

-if the counterfeit was in group A or B (last round):

1) Even: the counterfeit is in group B. depending on how the scale tipped during the last round, the counterfeit is heavier or lighter then the average coin.

2) Uneven: the counterfeit is in group A and depending on which way the scale is tipping, the counterfeit is heavier or lighter than the average coin.

-if the counterfeit is in group C (last round):

1) Tipping towards A: the counterfeit is lighter.

2) Tipping towards C: the counterfeit is heavier.

third....

i give up

Link to comment
Share on other sites

  • 0

So here we go…

Again, this is the solution for the 39 coins scenario. I highly recommend making a tree to follow along.

Separate in 3 sets of 13: Set X (coins 1-13), Set Y (coins 14-26), Set Z (coins 27-39)

H: Heavy

L: Light

P: # of possibilities

1st weighing: Y vs. Z [P = 78; either of the 39 coins can be H or L]

1a. Y vs Z unbalanced; Y is heavier

Coin is in set Y (14-26) and heavy or in set Z (27-39) and light; hence P=26. Weighings left 3; 3^3=27>26.

2nd weighing:
Move 9 coins from set Z to Y, Y to X, and X to Z. I'll say X1, Y1, and Z1 to distinguish.

Composition now is: set X1 (coins 1-4,18-26), set Y1 (14-17,31-39), set Z1 (27-30, 5-13) Then weigh Y1 vs. Z1.

2a. Y1 vs. Z1 balances. Coin is in X1 (18-26) and heavy; P=9 [coins 18-26 are heavy]; 2 weighings left, 3^2=9.

Split coins 18-26 in 3 each sets: A (18-20), B (21-23), C (24-26).

3rd weighing:
B vs. C

3a. B vs. C balances. Coin is in A (18-20) and heavy. P = 3; 1 weighing left 3^1=3.

4th weighing:
Coin 18 vs. Coin 19

If 18 vs. 19 tips, we know that the heavier coin is in the lower pan. If it balances, then 20 is the heavier coin.

3b. B vs. C doesn't balance. B is heavier. Coin is in B (21-23) and heavy. P = 3. 1 weighing left 3^1=3.

4th weighing:
coins 22 vs 23. See above for 18 vs 19 to get similar conclusions.

2b. Y1 vs. Z1 unbalances; Y1 is heavier. Coin is either in Y1 (14-17) and heavy or in Z1 (27-30) and light. P = 8 (14-17 can be heavy; 27-30 can be light); weighings left 2; 3^2=9. 8<9.

Coin switcheroo again: rotate a set of 3 coins such that…Set D (14,28-30), Set E(27,1-3 or any of the 3 "normal" coins).

3rd weighing
: D vs E.

3a. D vs. E balances. Coin is in set (15-17) and heavy. P = 3. Weighings left 1; 3^1=3.

4th weighing:
15 vs. 17. See above; derive similar conclusions.

3b. D vs. E unbalanced; D is heavier. Coin 14 is heavy or coin 27 is light. P =2. Weighings left 1; 3^1=3.

4th weighing:
weight 14 vs. a normal coin. If it balances, the counterfeit is 27 and light. If not, then counterfeit is 14 and heavy.

3c. D vs. E unbalanced; E is heavier. Coins 28-30 are light. P = 3. Weighings left 1; 3^1=3.

4th weighing:
29 vs. 30. See above, derive similar conclusions.

2c. Y1 vs. Z1 unbalances; Z1 is heavier. Coins 31-39 are light. P=9. Weighings left 2; 3^2=9.

This is similar to situation 2a where we have 9 coins and we know if it's light or heavy.

1b. Y (14-26) vs. Z (27-39) balances. Coin is in Set X (1-13) and either light or heavy. P=26. 3 Weighings left; 3^3=27.

Split in sets of 4+1. F (1-4), G(5-8), H(9-12), (13).

2nd Weighing:
G vs. H.

2a. G vs. H unbalanced; G is heavier. Coin is in G and heavy or H and light. P=8. 2 weighings left; 3^2=9.

Now this is the same as 2b (under 1a) above, so follow a similar strategy to get the answer.

2b. G vs. H unbalanced; H is heavier. Same as 2a; just switch set names.

2c. G vs. H balances. Coin is either heavy or light in (1-4) or (13). P =10, 2 weighings left; 3^2=9.

THIS IS THE ONLY SITUATION I HAVE NOT BEEN ABLE TO RESOLVE. Answer to this seems similar to the scenario when the # of coins is raised from 39 to 40.

Question….are we allowed to split the coin? I know this is far fetched...lol

Prime, is this okay so far or am I totally off? I'll post back in a few hours if I come up with a solution for the last part.

Link to comment
Share on other sites

  • 0

So here we go…

Again, this is the solution for the 39 coins scenario. I highly recommend making a tree to follow along.

Separate in 3 sets of 13: Set X (coins 1-13), Set Y (coins 14-26), Set Z (coins 27-39)

H: Heavy

L: Light

P: # of possibilities

1st weighing: Y vs. Z [P = 78; either of the 39 coins can be H or L]

1a. Y vs Z unbalanced; Y is heavier

Coin is in set Y (14-26) and heavy or in set Z (27-39) and light; hence P=26. Weighings left 3; 3^3=27>26.

2nd weighing:
Move 9 coins from set Z to Y, Y to X, and X to Z. I'll say X1, Y1, and Z1 to distinguish.

Composition now is: set X1 (coins 1-4,18-26), set Y1 (14-17,31-39), set Z1 (27-30, 5-13) Then weigh Y1 vs. Z1.

2a. Y1 vs. Z1 balances. Coin is in X1 (18-26) and heavy; P=9 [coins 18-26 are heavy]; 2 weighings left, 3^2=9.

Split coins 18-26 in 3 each sets: A (18-20), B (21-23), C (24-26).

3rd weighing:
B vs. C

3a. B vs. C balances. Coin is in A (18-20) and heavy. P = 3; 1 weighing left 3^1=3.

4th weighing:
Coin 18 vs. Coin 19

If 18 vs. 19 tips, we know that the heavier coin is in the lower pan. If it balances, then 20 is the heavier coin.

3b. B vs. C doesn't balance. B is heavier. Coin is in B (21-23) and heavy. P = 3. 1 weighing left 3^1=3.

4th weighing:
coins 22 vs 23. See above for 18 vs 19 to get similar conclusions.

2b. Y1 vs. Z1 unbalances; Y1 is heavier. Coin is either in Y1 (14-17) and heavy or in Z1 (27-30) and light. P = 8 (14-17 can be heavy; 27-30 can be light); weighings left 2; 3^2=9. 8<9.

Coin switcheroo again: rotate a set of 3 coins such that…Set D (14,28-30), Set E(27,1-3 or any of the 3 "normal" coins).

3rd weighing
: D vs E.

3a. D vs. E balances. Coin is in set (15-17) and heavy. P = 3. Weighings left 1; 3^1=3.

4th weighing:
15 vs. 17. See above; derive similar conclusions.

3b. D vs. E unbalanced; D is heavier. Coin 14 is heavy or coin 27 is light. P =2. Weighings left 1; 3^1=3.

4th weighing:
weight 14 vs. a normal coin. If it balances, the counterfeit is 27 and light. If not, then counterfeit is 14 and heavy.

3c. D vs. E unbalanced; E is heavier. Coins 28-30 are light. P = 3. Weighings left 1; 3^1=3.

4th weighing:
29 vs. 30. See above, derive similar conclusions.

2c. Y1 vs. Z1 unbalances; Z1 is heavier. Coins 31-39 are light. P=9. Weighings left 2; 3^2=9.

This is similar to situation 2a where we have 9 coins and we know if it's light or heavy.

1b. Y (14-26) vs. Z (27-39) balances. Coin is in Set X (1-13) and either light or heavy. P=26. 3 Weighings left; 3^3=27.

Split in sets of 4+1. F (1-4), G(5-8), H(9-12), (13).

2nd Weighing:
G vs. H.

2a. G vs. H unbalanced; G is heavier. Coin is in G and heavy or H and light. P=8. 2 weighings left; 3^2=9.

Now this is the same as 2b (under 1a) above, so follow a similar strategy to get the answer.

2b. G vs. H unbalanced; H is heavier. Same as 2a; just switch set names.

2c. G vs. H balances. Coin is either heavy or light in (1-4) or (13). P =10, 2 weighings left; 3^2=9.

THIS IS THE ONLY SITUATION I HAVE NOT BEEN ABLE TO RESOLVE. Answer to this seems similar to the scenario when the # of coins is raised from 39 to 40.

Question….are we allowed to split the coin? I know this is far fetched...lol

Prime, is this okay so far or am I totally off? I'll post back in a few hours if I come up with a solution for the last part.

I'm rewriting everything under "1b" scenario of my previous post.

1b. Y (14-26) vs. Z (27-39) balances. Coin is in Set X (1-13) and either light or heavy. P=26. 3 Weighings left; 3^3=27.

Split in sets of 4, 5, 4+1normal. Sets: F (1-4), G(5-9), H(10-13, 14 or any one "normal" coin).

2nd Weighing:
G vs. H.

2a. G vs. H unbalanced; G is heavier. Coin is in G(5-9) and heavy or H (10-13) and light. P=9. 2 weighings left; 3^2=9.

Coin switcheroo one more time: rotate 3 coins such that….G1(8-9,10-12) and H1 (13,14-16)

3rd Weighing:
G1 vs. H1

3a. G1 vs. H1 unbalanced. G1 is heavier. Coin is in G1(8-9) and Heavy or H1(13) and light. P=3. 1 Weighing left, 3^1=3.

4th Weighing:
weight 8 vs. 9. The lower pan in the heavier coin. If it balances, then coin (13) is the light coin.

3b. G1 vs. H1 unbalanced. H1 is heavier. Coin is in G1 (10-12) and light. P=3, 1 weighing left, 3^1=3. This is a now a trivial case; see above for similar strategy.

3c. G1 vs. H1 balances. Coin is in set (5-7) and heavy. Again, P =3 and 1 weighing left. Trivial case.

2b. G vs. H balances. Coin is in F (1-4) either light or heavy. P=8, 2 weighings left, 3^2=9.

Split coins in sets of (1-3) and (4)

3rd Weighing:
(1-3) vs. (any 3 good coins).

3a. (1-3) is heavier. Coin is in these 3 and heavier. Trivial case with 1 weighing left.

3b. (1-3) is lighter. Coin is in these 3 and lighter. Trivial case with 1 weighing left.

3c. Balances. Counterfeit coin is (4); use another weighing to find out light or heavy.

Forgot to mention in the previous post that other scenarios resulting from the weighings are similar to the ones mentioned; just switch the set names.

Link to comment
Share on other sites

  • 0

Suicide has the solution, toughing it through the last variation, where everything balances to the end in the last post. Another challenge is to express the solution in simpler terms. I will try that a little later. Now Suicide is ready to solve 40. Don't bother describing the cases where one group of 13 is heavier than the other. You've done that already. Just go directly into the path where everything balances.

Link to comment
Share on other sites

  • 0

Thanks for checking my work; I know it was VERY hard to follow. I'll try writing better.

So for the solution for the 40th one; I can't find a solution UNLESS you add ONE more coin of REGULAR weight.

so now we have 41 coins. 40 (either H or L) and 1 definitely regular.

Split up the coins in sets of X(1-13), Y(14-27), and Z(28-40,41).

Now the solution is going to be similar to the 13 coin solution like I described under my revised post for "1b."

1st weighing: Y vs Z

1a. Y(14-27) vs. Z(28-40,41) unbalanced, Y is heavier.

Rotate 9 coins such that..Y1(23-27, 28-36), Z1(37-40, 41, 1-9)

2nd Weighing:
Y1 vs Z1

2a. balanced. Coin is in set (14-22) and heavy. we have two weighings left. This has been explained before.

2b. Unbalanced. Y1 is heavier. Coin is in Y1( 23-27) and heavy or in Z1 (37-40) and light.

Rotate 3 coins again such that....Y2(26-27,37-39), Z2(40, 41, 1-3).

3rd Weighing:
Y2 vs Z2

3a. Y2 vs Z2 balances. Coin is in set (23-25) and heavy. 1 weighing left; trivial.

3b. Y2 vs Z2 unbalanced; Y2 heavier. Coin is in Y2(26-27) and heavy or Z2(40) and light.

4th Weighing:
weigh (26) vs (27) and find out if either is heavy. If not, (40) is light.

3c. Y2 vs Z2 unbalanced; Z2 is heavier. Coin is in Y2(37-39) and light. 1 weighing left, trivial.

2c. Unbalanced; Z1 is heavier. Coin is in set (28-36) and light. Similar technique as 2a.

1b. Y(14-27) vs. Z(28-40,41) balances. Coin is in set X (1-13) either light or heavy. Use the same technique as my previous post of "1b" revision.

1c. Y(14-27) vs. Z(28-40,41) unbalanced, Z is heavier. Same as 1a.

I'm not sure if I can do this WITHOUT adding a coin. I would love to hear your thoughts Prime.

Link to comment
Share on other sites

  • 0

Thanks for checking my work; I know it was VERY hard to follow. I'll try writing better.

So for the solution for the 40th one; I can't find a solution UNLESS you add ONE more coin of REGULAR weight.

so now we have 41 coins. 40 (either H or L) and 1 definitely regular.

Split up the coins in sets of X(1-13), Y(14-27), and Z(28-40,41).

Now the solution is going to be similar to the 13 coin solution like I described under my revised post for "1b."

1st weighing: Y vs Z

1a. Y(14-27) vs. Z(28-40,41) unbalanced, Y is heavier.

Rotate 9 coins such that..Y1(23-27, 28-36), Z1(37-40, 41, 1-9)

2nd Weighing:
Y1 vs Z1

2a. balanced. Coin is in set (14-22) and heavy. we have two weighings left. This has been explained before.

2b. Unbalanced. Y1 is heavier. Coin is in Y1( 23-27) and heavy or in Z1 (37-40) and light.

Rotate 3 coins again such that....Y2(26-27,37-39), Z2(40, 41, 1-3).

3rd Weighing:
Y2 vs Z2

3a. Y2 vs Z2 balances. Coin is in set (23-25) and heavy. 1 weighing left; trivial.

3b. Y2 vs Z2 unbalanced; Y2 heavier. Coin is in Y2(26-27) and heavy or Z2(40) and light.

4th Weighing:
weigh (26) vs (27) and find out if either is heavy. If not, (40) is light.

3c. Y2 vs Z2 unbalanced; Z2 is heavier. Coin is in Y2(37-39) and light. 1 weighing left, trivial.

2c. Unbalanced; Z1 is heavier. Coin is in set (28-36) and light. Similar technique as 2a.

1b. Y(14-27) vs. Z(28-40,41) balances. Coin is in set X (1-13) either light or heavy. Use the same technique as my previous post of "1b" revision.

1c. Y(14-27) vs. Z(28-40,41) unbalanced, Z is heavier. Same as 1a.

I'm not sure if I can do this WITHOUT adding a coin. I would love to hear your thoughts Prime.

No, you are not allowed to add any coins. I agree that if you pull a true coin out of your pocket and add to the set, you can solve the problem. You are trying to reuse the same trick, that you have found when solving 39 coins. Namely, when you had 3 weighings left and a set of 13 coins with undetermined fault (heavy or light) and you used a reference coin to isolate 9 coins instead of 8. (The very thing that separated my problem from the one where you solve 12 coins in 3 weighings.)

The trick for solving 40 is different. I’ll give a small hint here, after which you should solve it with ease. Check it out, if you like:

Read the statement of the problem again.

After that we shall revisit your proposition that you can always solve 81 or less possible cases with 4 weighings.

Link to comment
Share on other sites

  • 0
No, you are not allowed to add any coins. I agree that if you pull a true coin out of your pocket and add to the set, you can solve the problem. You are trying to reuse the same trick, that you have found when solving 39 coins. Namely, when you had 3 weighings left and a set of 13 coins with undetermined fault (heavy or light) and you used a reference coin to isolate 9 coins instead of 8. (The very thing that separated my problem from the one where you solve 12 coins in 3 weighings.)

The trick for solving 40 is different. I'll give a small hint here, after which you should solve it with ease. Check it out, if you like:

Read the statement of the problem again.

After that we shall revisit your proposition that you can always solve 81 or less possible cases with 4 weighings.

So rereading the problem, it seems I'm only to find the counterfeit coin and not if it's heavy or light.

I'll post a solution if I come up with it later....

As far as the proposition goes, I think you can always tell M^N cases apart when there are M mutually exclusive collectively exhaustive outcomes for each test and there are N tests GRANTED we can do the required N tests to have the 1 to 1 correspondence needed to make it work. For example, we couldn't do that in the above problem (the one I misinterpreted as finding the right coin out of 40 as well as if it's H or L) since coins are not divisible for us to use the balance effectively to gain that 1-1 correspondence of each test combination to each of the possible 80 cases. I added a coin so I can perform the required N (=4) tests to find the answer. Am I missing something there?

Link to comment
Share on other sites

  • 0

My daughter charges that I was not entirely fair with my second problem (40 in 4). To clear the air, but without admitting to any wrongdoing, I will stipulate as following:

My "spoiler" in my previous post is neither a solution, nor any part of the solution. Feel free to peek.

Link to comment
Share on other sites

  • 0
As far as the proposition goes, I think you can always tell M^N cases apart when there are M mutually exclusive collectively exhaustive outcomes for each test and there are N tests GRANTED ...

I am not sure… Sounds like what you say is, the problem can be solved if it can be solved. Isn’t the set of mutually exclusive tests with collectively exhaustive outcomes, the very thing that the problem asks you to find?

Regard 4 coins, where either only one can be either heavier, or lighter, or all four of them may be true. There are 9 combinations in all: 4 cases where one of the coins is heavier, 4 cases where one is lighter, and one case with all four of them true. Yet, I’m convinced that in two weighings (each with 3 distinct outcomes), you are not guaranteed even to find which one is counterfeit, if any, let alone tell whether it is heavier, or lighter. Despite the fact that 2 weighings have a potential to distinguish 3**2=9 cases.

Check out my posts in the “Weghing in a harder way” puzzle. That was the topic, which prompted me to come up with this weighing problem.

Link to comment
Share on other sites

  • 0

Now included with "rereading"...

Split coins in X(1-14), Y(15-27), Z(28-40).

I've already solved the case where the first weighing of 13vs 13 is unbalanced.

So I'll focus on the scenario when the 1st two sets (say Y and Z) have been weighed and were found to be balanced.

So coin is in X(1-14) either H or L and we have 3 weighings left.

Split coins in X1(1-5) and X2(6-14).

2nd Weighing: X2 vs. Y2(15-23)

2a. X2 vs. Y2 balances. Coin is in X1(1-5) either H or L.

Split coins in X3(1-2) and X4(3-5).

3rd Weighing: X4 vs. Y3(15-17)

3a. X4 and Y3 balances. Coin is X3(1-2). Use the last weighing with a good coin to find out the couterfeit. If lucky, you may find out if it's light or not if the last weighing doesn't balance.

3b. X4(3-5) and Y3(15-17) don't balance; X4 is lighter. Coin is in X4 and light. Trivial case with 1 weighing left.

3c. X4(3-5) and Y3(15-17) don't balance, Y3 is heavier. Coin in in X4 and heavy. Trivial case again.

2b. X2 vs Y2 unbalanced. X2 is heavier. Coin is in X2 (6-14) and heavy.

Split coins in sets of 3...(6-8), (9-11), (12-14).

3rd weighing: (6-8) vs (9-11)

3a. balances. coin is in (12-14) and heavy. Trivial case with 1 weighing left.

3b. unbalanced. Take the heavier pan with 3 coins and use the last weighing between two of them to find out the counterfeit.

2c. X2 vs Y2 unbalanced. X2 is lighter. This is the same as 2b.

I think that solves this problem.

Regarding your question of finding counterfeit in 4 coins within 2 weighings. I think you are confusing the number of possible outcomes. There are two scenarios that you are vaguely mentioned and they are quite different:

Scenario 1) 4 coins, 1 of the 4 is either lighter of heavier. Hence, the possible cases are that either of the 4 are either lighter or heavier (8 total possible cases). Since it's only ONE of these is counterfeit, these 8 cases are mutually exclusive and collectively exhaustive since if one is found counterfeit, the rest are true coins by default. To solve this one, you will need THREE more true coins. Do 3 (possible counterfeit) vs. 3 (normal ones). Note if it is heavy or light. Deduce from 3 possible scenarios to 1 with the next weighing. If it balances, the 4th possible coin is the counterfeit, use the last weighing to find out if heavy or light. This is what I meant. It is the fact that the test is not perfect and it has limitations which makes it necessary to add more coins to have the 1-1 correspondence of answers.

Scenario 2) This is the one where it's confusing. You mention at the end that ALL of them can be true. This changes the number of possibilities from 8 to 12. With 2 weighings, it is not possible to find out the counterfeit.

I hope that clarifies what I meant. Please let me know if I missed something above.

Link to comment
Share on other sites

  • 0

Suicide has the solutions to both puzzles.

I was given a “classical” variation of that problem 40 some years ago by my grandfather, who got it from his grandmother, when he was a little kid. There are 9 like bags, one with gold and 8 with sand. The bags with sand weigh the same, while the bag with gold is slightly heavier. Find the bag with gold with 2 weighings, or less on a balance-scale.

To solve, you put 3 bags into one pan, 3 into another, leaving 3 on the side. If one triplet outweighs another – that’s where we have to look for gold. If they weigh the same, the gold is in the triplet on the side. Then we weigh one bag from the isolated triplet against another, leaving one bag on the side. The problem is solved.

It works for powers of 3, like 27 bags in 3 weighings, 81 in 4, and so on. What’s interesting, the problem works for any mixture of heavy/light potential faults. For example, you have 3 coins and you know that only one is counterfeit, and you are also given that if it is the first coin, then it lighter, otherwise – it is heavier. (LHH set). Then you drop one potential heavy coin into one pan, another potentially heavy on the other side of the balance scale. And the heavier side is the counterfeit, or if they balance, then it must be the coin on the side and it is lighter. It works for any combination of H/L for any power of 3 for the number of coins. For example, if you have 9 coins with only one counterfeit and their potential faults are: (LLLLLHHHH). Then you weigh HHL against another HHL leaving the remaining LLL on the side. And on the second weighing the problem is solved. You can try it with any other combination to satisfy that it works.

Now to 3**N discussion. In my example with 4 coins (post #15) there are 9 different cases, not 12. There is only one case of all four coins being true. Much like when you roll a pair of dice, there are two variations to roll (5,6), but only one – (6,6).

But forget about all coins being true for now. Let’s say, one of them has to be counterfeit and is either heavier, or lighter. So there are 8 different cases for 4 coins, right? However, you still can not solve them in 2 weighings.

The catch here is whether it is possible to exclude enough cases on a given weighing, so that you remain within 3**N boundary for the remaining N weighings. That is not always possible, as my example with 4 coins/2 weighings illustrates.

In my “39 in 4” problem, the tricky situation was 13 coins of undetermined fault with 3 weighings left. The trick was to weigh 9 coins from that set, not 8. For that you’d have to use a reference (true) coin, which was available at that point. As Suicide had found (post #9, spoiler 2).

I think this discussion has beaten the balance-scale type problem into the ground. We could stomp on it a little more and then put it to rest. No other balance scale problems shall be posted, unless you find something new, clever, and different therein.

P.S. Of course, the Weight Problem of Bachet de Meziriac, published in 1624, where a merchant drops a 40-pound weight, which breaks into four uneven pieces, is different and more interesting.

Link to comment
Share on other sites

  • 0

You are right; this has been beaten to the ground.

Few parting points:

1) the number of possibilities, as you mentioned, above is indeed 9. I wonder what I was thinking.

2) And I think we agree that it works for only factors of 3's. This is what I meant by "limitation of the test" (you did a great good job explaining it and expanding it to general scenarios) and why I suggested to overcome the limitation by either dividing coins or adding more reference coins to get to that magical factor of 3 as I did to solve the 4coins/2weighing problem above.

Keep the good puzzles coming. I thoroughly enjoyed this one (and the chess one; we need more chess puzzles).

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...