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

• GCT
In summary, the conversation discusses a problem involving identifying a bag of counterfeit coins among a group of identical bags. Participants suggest different strategies and try to determine the maximum value of N, the number of bags, that can be accommodated in the problem. The final answer is determined to be N=7491.
GCT
Homework Helper
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?

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

And I only need to weigh once!

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

N=927 seems ok.

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.

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)

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.

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.

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

Icebreaker said:
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...

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:
Well, surely is more than my first guess N=927. I am going to think for a while.

Rogerio said:
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.

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

hmm well now I will have to think Rogerio.

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?

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

Icebreaker said:
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

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

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

Your first assumption is the correct one.

Well, my best guess is N=7491

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

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.

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

GeneralChemTutor said:
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.

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.

Last edited:
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.

Last edited by a moderator:
xorbie said:
...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.

Last edited:
Rogerio said:
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.

## 1. What is the significance of identifying the maximum number of bags with 3 weighings?

The maximum number of bags that can be identified with 3 weighings is an important problem in the field of combinatorics and optimization. It helps in understanding the efficiency and limitations of weighing methods and can have practical applications in industries such as logistics and transportation.

## 2. What is the maximum number of bags that can be identified with 3 weighings using traditional balance scales?

The maximum number of bags that can be identified with 3 weighings using traditional balance scales is 13 bags. This is because traditional balance scales can only compare the weight of two bags at a time, limiting the number of bags that can be compared in each weighing.

## 3. Can the maximum number of bags that can be identified with 3 weighings be increased with the use of modern weighing technology?

Yes, modern weighing technology such as digital scales and load cells can increase the maximum number of bags that can be identified with 3 weighings. This is because they can measure the weight of multiple bags simultaneously, reducing the number of weighings required to identify a larger number of bags.

## 4. How does the number of bags being weighed affect the maximum number that can be identified with 3 weighings?

The maximum number of bags that can be identified with 3 weighings is dependent on the number of bags being weighed. As the number of bags increases, the maximum number that can be identified decreases. This is because more bags require more weighings to compare all possible combinations.

## 5. Are there any known solutions for identifying the maximum number of bags with 3 weighings?

Yes, there are known solutions for identifying the maximum number of bags with 3 weighings, such as the trisection method and the ternary search method. These methods use a systematic approach to divide the bags into groups and weigh them in a specific order to maximize the number of bags that can be identified with 3 weighings.

• General Discussion
Replies
2
Views
2K
• General Discussion
Replies
10
Views
1K
• General Discussion
Replies
14
Views
6K
• General Discussion
Replies
9
Views
4K
• Math Proof Training and Practice
Replies
60
Views
8K
• General Discussion
Replies
9
Views
5K
• Math Proof Training and Practice
Replies
82
Views
12K
• General Discussion
Replies
45
Views
6K
• General Math
Replies
6
Views
7K
• Programming and Computer Science
Replies
1
Views
1K