[Guest]

This is similar to this week's Car Talk puzzler, but with an added wrinkle.

You have 7 stacks of 100 coins each. There is a possibility that some (or all, or none) of the coins are counterfeit. If there are any counterfeit coins, whole stacks will be counterfeit. That is, no stack contains both real and counterfeit coins; either a stack is all real, or all counterfeit. However, you DON'T know how many stacks are counterfeit, and you DON'T know how much counterfeit coins weigh. You DO know that real coins weigh 10 grams, all counterfeit coins weigh the same, and counterfeit coins are heavier than real coins and weigh an integer number of grams.

At your disposal is a standard digital bathroom scale. How many weighings on the scale do you need to determine which stacks are counterfeit and what counterfeit coins weigh?

Obviously it would be easy with 7 weighings: just weigh one coin from each stack in turn. I've figured out a way to do it in only 2 weighings. I'm not sure if it's possible to do it in 1, but give it a try!

[Guest]

Please clarify this statement .You DO know that real coins weigh 10 grams, all counterfeit coins weigh the same,

[Guest]

This only works if they are all real...but, weigh the whole pile together. If it weighs 700 grams, then all the coins are real, and there are zero stacks of counterfeit coins.

[Guest]

Please clarify this statement .You DO know that real coins weigh 10 grams, all counterfeit coins weigh the same,

Hey docbagby. I meant that all counterfeit coins weigh the same as each other, not the same as the real coins. So the real coins weigh 10 grams, and the counterfeit coins could all weigh 11 grams, or all weigh 50 grams, or all weigh 14 grams, etc. Sorry for the confusion!

[Guest]

This only works if they are all real...but, weigh the whole pile together. If it weighs 700 grams, then all the coins are real, and there are zero stacks of counterfeit coins.

If it only works if they're all real, it doesn't work.

[Guest]

Hey docbagby. I meant that all counterfeit coins weigh the same as each other, not the same as the real coins. So the real coins weigh 10 grams, and the counterfeit coins could all weigh 11 grams, or all weigh 50 grams, or all weigh 14 grams, etc. Sorry for the confusion!

Thank you for that clarification.

[Guest]

Not sure if this is exactly right but I think it's in the right direction. Of stacks A through G, put one coin from A, two from B, three from C,etc, to 7 from G. Then reverse it (seven from A, six from B,...,one from G). I THINK you get unique solutions (I'd need to work it out on paper). If not, then it should work with different sizes of stacks to make them unique.

[Guest]

If it only works if they're all real, it doesn't work.

So, by your logic, if something only works one way, then it doesn't work at all....then if you can only eat fruit when you're awake, then you can't eat fruit?

Sorry, but if you're going to say that a solution doesn't work because it doesn't work in every way you want it to, and you don't like my goofy solution, then you should be more specific when asking for solutions.

Edited April 23, 2011 by jkdecd03

[Guest]

1

Edited April 23, 2011 by jkdecd03

[Guest]

So, by your logic, if something only works one way, then it doesn't work at all....then if you can only eat fruit when you're awake, then you can't eat fruit?

Sorry, but if you're going to say that a solution doesn't work because it doesn't work in every way you want it to, and you don't like my goofy solution, then you should be more specific when asking for solutions.

But your solution only works if the first weighing results in one specific way. What happens if it doesn't weigh 700 grams? You don't explain that. So your solution is grossly incomplete.

[Guest]

But your solution only works if the first weighing results in one specific way. What happens if it doesn't weigh 700 grams? You don't explain that. So your solution is grossly incomplete.

I didn't say it was complete...I said "this is ONE way to do it." Therefore, if it doesn't give you your answer, then you find another way to do it. Also, it DOES work in the situation when all the coins are real. So don't say it doesn't work. It just doesn't apply to all possible situations. And I never said it did. Sheesh. I can't believe we're getting in a fight on a forum. This is lame. All I did was pose one possible solution to one possible situation. If you don't like it, then stick it.

Edited April 23, 2011 by jkdecd03

[Guest]

Place all seven stacks on the scale. That's one weighing. If they weigh something over 7000 grams (1 kg/bag), remove one stack at a time. At some point, the weight will change until the total is 1 kg/per stack. As each stack is removed, if the weight doesn't change, you know that stack is not counterfeit. If the weight does change, you know the stack is counterfeit. Continue until you have separated the stacks into two piles. Seems to me that's one weighing.

As each counterfeit stack is removed, you will also know it's weight.

P.S. If I had a hundred coins, I'd but them in sacks or bags, not stacks.

Edited April 24, 2011 by jws3

[plainglazed]

I didn't say it was complete...I said "this is ONE way to do it." Therefore, if it doesn't give you your answer, then you find another way to do it. Also, it DOES work in the situation when all the coins are real. So don't say it doesn't work. It just doesn't apply to all possible situations. And I never said it did. Sheesh. I can't believe we're getting in a fight on a forum. This is lame. All I did was pose one possible solution to one possible situation. If you don't like it, then stick it.

okay, usually dont chime in on this type of thing but feel it's worth saying that there is really no reason to get huffy. the OP is clearly looking for a universal solution. to define the outcome and then give one "solution" to that outcome is trivial.

This only works if they are all real...but, weigh the whole pile together. If it weighs 700 grams, then all the coins are real, and there are zero stacks of counterfeit coins.

moreover, your solution is impossible for any situation per the parameters of the OP. maybe you meant 7000.

I dont think it is possible to do it in one weighing without putting some ceiling on the weight of the counterfeit coins. seems you can always have a counterfeit weight that is equal to the product of two stack counts. say you weigh 1,2,3,4,5,6,7 coins from the seven stacks, respectively. if the counterfeit weight was 42 the total weight could indicate either stack from which 6 were taken, or 7, or both are counterfeit. for that matter, the quantity of coins weighed from each stack and 10 could all be multiples of the counterfeit weight which would reveal no information.

Edited April 24, 2011 by plainglazed

[Smith]

I can answer the first part of the question, but the second part is beyond me.

Call the stacks A...G. Place ONE coin from A, TWO from B, FOUR from C, EIGHT from D, SIXTEEN from E, THIRTY-TWO from F, and SIXTY-FOUR from G onto the scale. As there are now 127 coins on the scale, if every coin is genuine the total weight will be 1270 grams. If there are any sets of counterfeit coins, their ADDITIONAL weight (the amount greater than 1270 grams) will be a multiple of a number from 1 to 127.

For starters, let's assume the weight of a counterfeit coin is 11 grams. The total weight will fall between 1270 (all genuine) and 1397 (all counterfeit). The actual number will indicate the stack(s) which contain counterfeit coins.

Looking at the number > 1270 indicates the stacks as follows:

1 = A

2 = B

3 = A+B

4 = C

5 = A+C

6 = B+C

7 = A+B+C

8 = D (etcetera)

Now if the weight of a counterfeit coin is 11 grams, we have our answer in one weighing. However, if the weight of a counterfeit coin exceeds 11 grams, there are various duplicate sums which could lead to multiple solutions. For example, a total weight of 1306 = 1270 + 36. 36 extra grams could mean:

Stacks C+F contain 11 gram counterfeits

Stacks B+E contain 12 gram counterfeits

Stacks C+D contain 13 gram counterfeits

Stacks A+D contain 14 gram counterfeits

Stacks B+C contain 16 gram counterfeits

Stack C contains 19 gram counterfeits

Stacks A+B contain 22 gram counterfeits

Stack B contains 28 gram counterfeits

Stack A contains 46 gram counterfeits

As to the question of the minimum number of weighings needed to determine the true weight of the counterfeits, that aspect of the solution escapes me. Just looking at the combinations for a number like 36 created so many possible solutions... and the question is open-ended regarding the possible weights of a counterfeit coin. I leave the further solution to better minds.

Oh, and please do not submit MY answer to Car Talk - that would be CHEATING!

[Guest]

Begin as Smith said:

For the first weighing:

From stack A take 1 coin

From stack B take 2 coins

From stack C take 4 coins

From stack D take 8 coins

From stack E take 16 coins

From stack F take 32 coins

From stack G take 64 coins

If there are no counterfeit coins, the weight should be 1270 grams. Look at how many grams above 1270 you are, and figure out all the possible combinations of stacks that could have produced that. For example, if you're 20 grams over, that could be either the 1 coin from A (30 grams), the 2 coins from B (20 grams each), the 4 coins from C (15 grams each), the 10 coins from B and D (12 grams each), or the 20 coins from C and E (11 grams each).

Now, for the second weighing:

Take ONE coin from each of the stacks that are possible above. In our example, take 1 coin from A, B, C, D, and E. However many grams you're over now, look at the results of the first weighing to determine which stack or stacks are responsible. For example, if you're now over by 5 grams, the only counterfeit stack is C (since each of those weighs 5 grams over). If you're over by 4 grams, the counterfeit stacks are B and D (since each of those weighs 2 grams over).

Hope this makes sense!

[Guest]

It only takes one weighing.

Remember, we're only looking at the overweight, which is 127 grams if all are bad.

1 coin from stack 1

2 from 2

4 from 3

8 from 4

16 from 5

32 from 6

64 from 7

If weight is 1270 grams, all are good.

If all are counterfeit, the overweight would be 127 grams.

If overweight is odd, stack one is couterfeit.

Any overweight can only be a unique combination of some (or all) of the numbers above, readily identifying the bad stacks.

Begin as Smith said:

For the first weighing:

From stack A take 1 coin

From stack B take 2 coins

From stack C take 4 coins

From stack D take 8 coins

From stack E take 16 coins

From stack F take 32 coins

From stack G take 64 coins

If there are no counterfeit coins, the weight should be 1270 grams. Look at how many grams above 1270 you are, and figure out all the possible combinations of stacks that could have produced that. For example, if you're 20 grams over, that could be either the 1 coin from A (30 grams), the 2 coins from B (20 grams each), the 4 coins from C (15 grams each), the 10 coins from B and D (12 grams each), or the 20 coins from C and E (11 grams each).

Now, for the second weighing:

Take ONE coin from each of the stacks that are possible above. In our example, take 1 coin from A, B, C, D, and E. However many grams you're over now, look at the results of the first weighing to determine which stack or stacks are responsible. For example, if you're now over by 5 grams, the only counterfeit stack is C (since each of those weighs 5 grams over). If you're over by 4 grams, the counterfeit stacks are B and D (since each of those weighs 2 grams over).

Hope this makes sense!

[Guest]

Think of it a a 7-bit binary number, in which any number between 0 and 127 can be represented by ones and zeroes.

A one is a counterfeit stack.

And the Car Talk puzzler clearly states that good coins weigh 10 grams and counterfeit coins weigh 11 grams.

Plus they said in part two it takes one weighing.

http://www.cartalk.com/content/puzzler/transcripts/201117/index.html

It only takes one weighing.

Remember, we're only looking at the overweight, which is 127 grams if all are bad.

1 coin from stack 1

2 from 2

4 from 3

8 from 4

16 from 5

32 from 6

64 from 7

If weight is 1270 grams, all are good.

If all are counterfeit, the overweight would be 127 grams.

If overweight is odd, stack one is couterfeit.

Any overweight can only be a unique combination of some (or all) of the numbers above, readily identifying the bad stacks.

[superprismatic]

Think of it a a 7-bit binary number, in which any number between 0 and 127 can be represented by ones and zeroes.

A one is a counterfeit stack.

And the Car Talk puzzler clearly states that good coins weigh 10 grams and counterfeit coins weigh 11 grams.

Plus they said in part two it takes one weighing.

http://www.cartalk.com/content/puzzler/transcripts/201117/index.html

What's that Car Talk site have to do with it? The OP clearly states that we do not know the weight of the counterfeit coins except that they all weigh the same and that each weighs an integer number of grams larger than 10. That is the problem we are considering here.

[Peekay]

The binary process is the best one for problems of these types. But it works with one weighing only if the weight of the counterfeit coins is known. Since this is not the case, the second weighing is necessary!

[Guest]

...two weighings.

Assign each stack with a different value 0 to 6.

Take 2ⁿ coins from stack n for each stack.

Weigh the 127 coins as one unit. Subtract 1270 to obtain the difference in the weight of the real coins and those counterfeit.

Take 1 coin from each stack.

Weigh the 7 coins. Subtract 70 to obtain the difference in the weight of the real coins and those counterfeit.

If the difference is greater than 0, one or more stacks are counterfeit. Dividing the differences in the weights of the 127 coins and the 7 coins one can map the result to one of the 5040 binary combinations and determine which of the seven stacks were counterfeit, and by knowing the quantity of counterfeit stacks, could then deduce the weight of each counterfeit coin.

[Guest]

to be solvable in this approach:

Let x be the difference between weights of a counterfeit coin and a real one,

as x is unknown and without upper limit, x can be the product of any numbers.

e.g. x = 127! which is a common multiple of 1,2,3,4,5,......125,126and127,

and covers any combination your method can brought, and it's impossible to tell which stack is fake.

Although (127!+10)g is too big to imagine for the weight of a coin, but your

question did allow this possiblity, and I doubt that there won't be any method

lead to a solution for less than the basic 7 weighings(for cases: all real and only last is fake).

For modification, the difference x should be limited, says >5, and the number of coins in each stack may increase(even to infinity). But beware the proving work would not be easy. Good luck.

Begin as Smith said:

For the first weighing:

From stack A take 1 coin

From stack B take 2 coins

From stack C take 4 coins

From stack D take 8 coins

From stack E take 16 coins

From stack F take 32 coins

From stack G take 64 coins

If there are no counterfeit coins, the weight should be 1270 grams. Look at how many grams above 1270 you are, and figure out all the possible combinations of stacks that could have produced that. For example, if you're 20 grams over, that could be either the 1 coin from A (30 grams), the 2 coins from B (20 grams each), the 4 coins from C (15 grams each), the 10 coins from B and D (12 grams each), or the 20 coins from C and E (11 grams each).

Now, for the second weighing:

Take ONE coin from each of the stacks that are possible above. In our example, take 1 coin from A, B, C, D, and E. However many grams you're over now, look at the results of the first weighing to determine which stack or stacks are responsible. For example, if you're now over by 5 grams, the only counterfeit stack is C (since each of those weighs 5 grams over). If you're over by 4 grams, the counterfeit stacks are B and D (since each of those weighs 2 grams over).

Hope this makes sense!

[curr3nt]

Let y = weight of 7 coins - 70

Let z = weight of 127 coins - 1270


[1] = 1, 2, 4, 8, 16, 32, 64

[2] = 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96

[3] = 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112

[4] = 15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120

[5] = 31, 47, 55, 59, 61, 62, 79, 87, 91, 93, 94, 103, 107, 109, 110, 115, 117, 118, 121, 122, 124

[6] = 63, 95, 111, 119, 123, 125, 126

[7] = 127


For s = 7 To 1 Step -1

  If y Mod s = 0 Then

    x = y / s

    If z / x In [s] Then 

      Msg s & " stacks have counterfeits weighing " & x + 10

Next


The number it matches in the set corresponds to a stack arrangement.


To disprove we need to find a value of y and z which give more than one solution.  Off I go to actually write a script to play with!

[curr3nt]

Counterfeit = 14 and Stacks A, C & G = 1546 and 82

Counterfeit = 13 and Stacks C, D, E & G = 1546 and 82


Counterfeit = 13 and Stacks C, D, F & G = 1594 and 82

Counterfeit = 14 and Stacks A, E & G = 1594 and 82


Counterfeit = 13 and Stacks A, B, E, F & G = 1615 and 85

Counterfeit = 15 and Stacks A, C & G = 1615 and 85


Could someone double check my calculations?

[Guest]

This only works if they are all real...but, weigh the whole pile together. If it weighs 700 grams, then all the coins are real, and there are zero stacks of counterfeit coins.

I don't think this is quite right...if you arrive at 700 grams for 700 coins where authentic coins weigh 10g each, then you have in one weighing determined that all 700 are fake...seeing as 10g * 700 coins = 7000g or 7kg

[Guest]

...two weighings.

Assign each stack with a different value 0 to 6.

Take 2ⁿ coins from stack n for each stack.

Weigh the 127 coins as one unit. Subtract 1270 to obtain the difference in the weight of the real coins and those counterfeit.

Take 1 coin from each stack.

Weigh the 7 coins. Subtract 70 to obtain the difference in the weight of the real coins and those counterfeit.

If the difference is greater than 0, one or more stacks are counterfeit. Dividing the differences in the weights of the 127 coins and the 7 coins one can map the result to one of the [correction:] 127 binary combinations and determine which of the seven stacks were counterfeit, and by knowing the quantity of counterfeit stacks, could then deduce the weight of each counterfeit coin.

I found an error in my solution. If p equals the weight of the 127 coins and n equals the weight of the 7 coins, then p/n results in duplicates for the following binary combinations:

-------- p- n p/n

1000101 069 3 23

1011100 092 4 23

1110011 115 5 23

1010001 081 3 27

1101100 108 4 27

By increasing the number of coins from stack 5 (2^5) to 47 and stack 6 (2^6) to 94, one can eliminate the duplicates, and create unique results for p/n thereby acquiring the desired deducement in weighing of the 172 coins and 7 coins.

[Guest]

What's that Car Talk site have to do with it? The OP clearly states that we do not know the weight of the counterfeit coins except that they all weigh the same and that each weighs an integer number of grams larger than 10. That is the problem we are considering here.

I am very sorry. I thought this was about the Car Talk puzzler, as referenced in more than one post.

That's the answer I postulated.

Going back, the OP puzzle is not solvable with any cleverness, so it's irrelevant.