What is the maximum number of bags that can be identified with 3 weighings?

[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?

 

[Galileo]

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

And I only need to weigh once!

 

[GCT]

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

 

[Rogerio]

N=927 seems ok.

 

[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.

 

[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)

 

[Davorak]

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

 

[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.

 

[Icebreaker]

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

 

[Rogerio]

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

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...

 

[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.

 

[Rogerio]

Well, surely is more than my first guess N=927. I am going to think for a while.

 

[Icebreaker]

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...

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

 

[Rogerio]

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

 

[Davorak]

hmm well now I will have to think Rogerio.

 

[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?

 

[gerben]

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

400

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

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

 

[GCT]

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

 

[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.

 

[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.

 

[GCT]

Your first assumption is the correct one.

 

[Rogerio]

Well, my best guess is N=7491

 

[GCT]

Your answer seems correct, did you cheat and find it off the net (which one can do for any brain teaser these days)?

 

[GCT]

I ask this because most people who do not get this right within the first try don't get the answer at all (unless they were quite close the first time). Part of the explanation being that it requires for one to be fairly fluent with number theory. Your first answer was a far cry from your answer now.

 

[gerben]

since the answer is out now, can someone explain it?

 

[Rogerio]

Your first answer was a far cry from your answer now.

After my first answer, I realized I could change the weighing method for the 2 first steps, and then I extended it for all the three steps.

 

[xorbie]

I don't actually know any number theory, but I think I've figured out how, generally speaking, to do this.

At any rate, I'm fairly sure that N=256 for 2 weighings (and I know for certain I can get 256).

The method I'm using (at least tell me if I'm on the right track): There are 64 different rational numbers a/b where a,b are both in [1,10]. Let's say that the difference in masses between the counterfeit and real coins is M. Now of course what we are going to do is separate up the original 256 into groupings of 1 from some bags, 2 from other bags and so on. Let's say that the number (mod 64) of our counterfeit bag is n. Let x be the number we take out of bag n for the first time on the scale. Let y be the number we take out of bag n the second time around. Then A=x*M and B=y*M will be what the scale reads out. Thus so long as we have set it up so that A/B = x/y will always be unique from any other possible x/y, then we will know precisely which bag it is.

Here's how many sacks start with each chip amount (goes from 1-->10):

(40,20,28,20,32,16,36,20,29,16). This ends up being (10,5,7,5,8,9,5,7,4) after two weighings. Basically I increase the sacks that started with 1 chip by 1,2,3,4,5,6,7,9 or 10 (so each sack is unique, because I'll end up with A/B as either 1,1/2,1/3, etc). But then the sacks that started with 2 chips, I only increase by either 1,3,5,7 or 9 so that I don't repeat 1/2, 1/3, 1/4, etc and get only 2/3, 2/5, 2/7, 2/9 and 2. So on and so forth for the rest of the starting amounts.

This way, we generate every single of the distinct 64 rationals. So we go from 256->128->64 and one of those must be our bag, pointed to by it's rational number.

So yeah, that's my general method. Tough to explain here.

I'd like to know how to extend it to three steps... clearly you can do a lot of things with A, B and C, and I'm not sure how to find the number of unique outcomes.

 

[SGT]

If we know that the difference in weight is an integer number of grams, the number of bags that can be used is limited only by how many coins exist in each bag. And you need only two weightings.

 

[Rogerio]

...at least tell me if I'm on the right track

You are on the right track: if you have (1,3) then (2,6) is redundant, and so on.

Then, the way I did was: "consider each possible pair in [1,10] and eliminate those with common factors".

But I found only 63 different numbers a/b, a&b in [1,10]. However, for 2 weighings, you have N=257 : 127x127 at the first weighing, and 3 bags out.

To extend to 3 weighings, just consider all triples (a,b,c) , a&b&c in [1,10], and again eliminate the redundant sequences.

 

[xorbie]

You are on the right track: if you have (1,3) then (2,6) is redundant, and so on.

Then, the way I did was: "consider each possible pair in [1,10] and eliminate those with common factors".

But I found only 63 different numbers a/b, a&b in [1,10]. However, for 2 weighings, you have N=257 : 127x127 at the first weighing, and 3 bags out.

To extend to 3 weighings, just consider all triples (a,b,c) , a&b&c in [1,10], and again eliminate the redundant sequences.

That's what I was thinking, thanks.