# Coin weighing problem (ibm)

1. Feb 9, 2005

### GCT

Perhaps some of you have seen this before

A scale will report the difference, in grams, between the masses on the two sides, as well as telling you which side is heavier. So if you place 25 grams on the left pan and 27 grams on the right, you find out that the right side is heavier by 2 grams.

You are given N bags of coins, apparently identical. Each bag contains ten coins. Exactly one bag is full of counterfeit coins, and the rest are full of honest coins . All honest coins are equally massive, all counterfeit coins are equally massive, and counterfeit coins are heavier than honest coins. But you don't know beforehand the masses of honest coins or of counterfeit coins.

You are given the opportunity to make three weighings on your scale, after which you must decide which bag is bogus. You're allowed to open the bags and use an arbitrary number of coins from each bag, if that helps; just keep track of where you got the coins.

What is the largest value of N which can be accommodated?

2. Feb 10, 2005

### Galileo

Ooh! ooh! I know the answer for N=2.

And I only need to weigh once!

3. Feb 10, 2005

### GCT

Nope, N should be much much much larger. Note that this is of different nature than the coin problems before.

4. Feb 10, 2005

### Rogerio

N=927 seems ok.

5. Feb 10, 2005

### Icebreaker

N = 6. You start with 3 bags on each side. Each time there's a difference in weight, you remove one bag on each side. If after the bag is removed, the balance shows that the two sides are equal, then the counterfit ones are, of the two bags removed, the one that came from the heavier side.

6. Feb 10, 2005

### Icebreaker

On the first weigh, take one coin out of each bag and divide them into 2 equal groups. The heavier group is the one with the counterfit coin. Proceed to take one coin OFF the lighter side (counts as the second weigh?). The difference is now the mass of the counterfit coin. (If N is odd, hold on to one of the coins. If on the first weigh, the two groups are equal, then you are holding the counterfit.) With that information, you can get to N = 22, I think. (This is written in a hurry)

7. Feb 10, 2005

### Davorak

Well as long as you are allowed to cut up the coins in to 10/n pieces then you can find the counterfeit bag out of n number of bags.

8. Feb 10, 2005

### GCT

Rogerio is the closest, although I'm not going to say whether it's an under/overestimate. Some of you don't seem to be understanding the problem correctly.

9. Feb 10, 2005

### Icebreaker

Davorak is right. If you are allowed to cut the coins, then you can find the counterfit bag for any N.

10. Feb 10, 2005

### Rogerio

Cmon Iceb!

If you are allowed to use some chemical reagents, or maybe an electromagnetic field, or X rays, for example, you could find that bag with ZERO weighings, for any number of bags!

But we know these are not the correct answer...

11. Feb 11, 2005

### Davorak

Not cutting the coins.
I get:
2*2*19*20 = 1520

I think there is still should be a better way yet, but I have to figured it out yet. The better way may change that last 20 into a 2*19 or something similar. I will have to think on it some more. It is hard to prove that there is not a better way I will just have to try for trail and error. If a higher number of bags can be used in this problem I suspected that the weight difference between the normal coin and counterfeit coin would be found on the third weigh rather then the second weigh like mine.

Edit:
Knowing the weights of the coins it would be:
20*20*20 =8000

So 1520 seems reasonable or low.

Last edited: Feb 11, 2005
12. Feb 11, 2005

### Rogerio

Well, surely is more than my first guess N=927. Im gonna think for a while.

13. Feb 11, 2005

### Icebreaker

Ya, I was kidding. But it's waaaaaaay higher than I'd expected.

14. Feb 11, 2005

### Rogerio

My guess is N=5591 (without knowing the weights of the coins in advance)

15. Feb 11, 2005

### Davorak

hmm well now I will have to think Rogerio.

16. Feb 11, 2005

### Icebreaker

If you knew only the difference in weight, for what N can you weigh in 2 weighs?

If you knew the exact weight of the counterfit, for what N can you weigh in 1 weigh?

17. Feb 11, 2005

### gerben

400

20
EDIT: thanks Davorak (post #19), 20 is probably wrong here, my new guess is 3

Last edited: Feb 11, 2005
18. Feb 11, 2005

### GCT

All the suggestions so far are still under the real value, including Rogerio's.

19. Feb 11, 2005

### Davorak

gerben how do you get 20 for one weigh? 400 makes sense for the first part since you know the difference in weight of the counterfeit and the real coin, but in the one weigh problem you only know the weight of the counterfeit coin and not the weight of the normal coin.

If 10 groups(1,2,3,4,5,..10) from different bags is put on both sides of the scale it would read out the difference in weight times the number of counterfeit coins. But the difference in weight is unknown. So you can not tell the number of coins or the bag it came from.

Last edited: Feb 11, 2005
20. Feb 11, 2005

### Davorak

Question GeneralChemTutor, each time a difference is measured off the scale is considered a one weigh right? Or is each time you load up each side considered one weigh and you can sneak a peak at the weight when you put one on or the other. I have been working under the first assumption.