Find the Underweight Coins: A Coin-Shaving Challenge

[vikasj007]

i think that most of you people are smart enough to find the first part, a piece of cake.

WELL, HOLD ON!

that was just the warming up session. this one is the real cracker. let's see how good are you at this one.









You're sitting in your office, when your boss walks in, carrying a basket filled with bags. He picks up a bag and opens it, pouring five gold coins on your desk.

"The Mint asked us to find a coin-shaver," he says. "The Mint has exactly 81 different suppliers; one of them is consistently supplying underweight coins, but we don't know which one. He gestures to the bags. "Here," he says, "we have 81 bags each containing five coins; one bag from each supplier. We know that all the coins are absolutely identical, except for the coins from the one underweight bag. We don't know how much underweight these coins are, but we know they're all underweight by the same amount. I need you to find out which bag contains the underweight coins. And, I need you to find out in the minimum number of weighings. Get to work."

All you have to work with is your trusty two-pan scale. This fancy scale will report the exact difference in weight between masses placed in the two pans, as well as telling which side is heavier. That means you can tell exactly how much more or less one pile of coins weighs compared to another...but remember you don't know how much less the underweight coins weigh.

What is the minimum number of weighings required to find the one bag of underweight coins, if each of the 81 bags contains five coins? You can take individual coins out of bags and label them if you desire.

 

[AKG]

I don't see what's so hard about this. I'll try to get less than 4 weighings, but 4 is simple enough. Weight 27-27. If there's a balance, the remaining 27 have the bad bag, otherwise it is the one that weighs less. Take that group of 27, and weigh 9-9, then 3-3, then 1-1, and you're done. 4 weighings. I said I'd try to do less than 4, but I don't think it's possible.

 

[vikasj007]

That is a good effort, but you are using the same method as in the earlier question where there were 9 coins.

here the situation is different and although 4 seems to be a good enough answer, i am sure you can come up with something better.


P.S: is there nobody else who is trying to solve this?

 

[NateTG]

here the situation is different and although 4 seems to be a good enough answer, i am sure you can come up with something better.

It's possible to identify the coin in 3 weighings easily. It may be possible to do it in two, but the limit of 5 coins per bag makes it tricky.

 

[NateTG]

I don't think two weighings is possible:

Let's assume that there is a solution with two weigings.

Then if the first weighing balances, there must be, at most three bags left to deal with.

Therefore, the first weighing must involve at least 78 of the bags.

Similarly, the second weighing must involve at least 77 of the bags.

This method must handle the case where neither weighing balances. Now the possible results for the first weighing are
5x, 4x, 3x, 2x, 1x, -1x, -2x, -3x, -4x, or -5x
similarly for the second weiging the remaining possible results are:
5x 4x 3x 2x 1x...

However, since x is unknown, it's impossible to distinguish, for example, between 1x and 1x or 2x and 2x occurring on the consecutive weighings. That means that the result scapes can only share one negative, and one positive coefficient. This limits the number of possible results of the combined weighings to 36, but the method must handle at least 77.

 

[AKG]

It's possible to identify the coin in 3 weighings easily.

How would you do that?

 

[NateTG]

How would you do that?

It's pretty easy. I missed it the first time I read the problem, but it allows for the balance to indicate the difference, not just which side is heavier. Spoiler follows


=====SPOILER======

So, you can use one weighing to find out by how much the extra coins are short.
Then split the 81 bags into 9 groups of 9. For each bag in group 1 put 4 coins from the bag on the left side, for each bag in group 2 put 3 coins on the left side, and so on. That will restrict the short coin to one bag - from there you can do essentially the same thing again.


With enough coins per bag it's possible to find the bad bag with two weighings. The question is what the smallest number of coins is. For example, if each bag had 41 coins, then two weighings works quite easily, and, I'm fairily sure that there must be at least 8 coins in each bag in order to get two weighings because of my argument above.

 

[AKG]

Then split the 81 bags into 9 groups of 9. For each bag in group 1 put 4 coins from the bag on the left side, for each bag in group 2 put 3 coins on the left side, and so on. That will restrict the short coin to one bag - from there you can do essentially the same thing again.

I missed the bit about the scales telling you the difference, probably because I thought it was irrelevant, meaning I probably wouldn't have got the problem anyways. Anyways, I assume you mean something like this:

Group     No. of Coins    Side
1           5                   L
2           4                   L
.
.
.
8          3                    R
9          4                    R

And I also assume that you mean that this would tell you which GROUP the shaved coins are in, not which bag. After figuring out which group it's in, you can do a similar weight to figure out which bag it's in. I think, if there are 81 bags, then 40 is the minimum number of coins. Find the difference in the first weighing, then for n = 1 to 40, put n coins of bag n on the left, and for n = 41 to 80, put n-40 coins of bag n on the right. If there's a balance, it's bag 81.

EDIT: Oh wait, I noticed you said it would only take 8 coins to do it in 2 weighings. Now how would you do that?

 

[NateTG]

EDIT: Oh wait, I noticed you said it would only take 8 coins to do it in 2 weighings. Now how would you do that?

I said at least 8. The argument I have for two weighings being insufficient fails at that point but I haven't gone to the trouble of finding a method for doing it. Actually, there may be a problem with my argument. After the first weighing, we know that the coin is in one of 39 bags, not 1 of 78, since we know that the coin is lighter, my argument leads to narrowing it down to 36 of 38 which is *really* tight so now I'm stuck wondering if it's possible with 6 coins per bag.

Regarding a smaller number of coins:
Here is an example using 9 coins per bag:

Set three bags aside, split the remaining 78 into six groups of thirteen, and weigh them using 1,5, and 7 on each side. Clearly the case where the scale is balanced (3 bags and 1 weighing left) is easy, if one side is light, the counterfit must be in a bag represented on that side.

Now, you know that the counterfit coin is in one of 39 bags. Split these into 13 groups of 3, and add a group of 3 known good bags for balance. Then place 1,2,3,4,6,8,9 coins from a group on each side.

Now, take the ratio of the differences from the first two weighings. Since each pair of possible results produces a different ratio, you can find the difference between a regular and the counterfeit coins.

You can then go back and identify the results of both weighings to find which bag contains the counterfits.

 

[vikasj007]

well this being a pretty tiring task, i have not bothered to go through your answers, the answer is that it can be done in 2 weighings.


i'll still give you a chance to try it yourself, but for those who want to know the answer, here it is.







The minimum number of weighings required is two. Since you don't know the actual weight difference between real and underweight coins, you need to rely on the ratio of weight differences found during the two weighings. Here's how to do it:

Split the 81 bags into 19 groups of four, with five left over.
Label each of the 19 groups with one of the following sets of numbers, representing the number of coins to place in the scale in each weighing: 1/1, 1/2, 1/3, 1/4, 1/5, 2/1, 2/3, 2/5, 3/1, 3/2, 3/4, 3/5, 4/1, 4/3, 4/5, 5/1, 5/2, 5/3, and 5/4.
Label the four bags within each group with the following letters, representing which side of the balance to place the coins on: L/L, L/R, R/L, and R/R.
Label the last five bags as follows: (0/1, X/L), (0/1, X/R), (1/0, L/X), (1/0, R/X), and (0/0, X/X), where the 0 and X indicate no coins are to be weighed.
For the first weighing, take the number of coins indicated by the first number from each bag and place them on the side indicated by the first letter. For example, from the bag labeled (3/2, R/L), place three coins onto the right side of the balance. For bags that have a 0 in the first position, do not weigh any coins.
Note that for every bag labeled R, there is one corresponding bag labeled L in the same group. Thus the same number of coins end up on each side, and any weight difference is due solely to the underweight coins. After placing all coins in the correct pan, record the difference in weight between the two sides.
Repeat the procedure for the second weighing, using the second number and letter. Again record the difference in weight between the two sides.
There are three possible outcomes. First, if both weighings showed the two sides equal in weight, then the bag labeled (0/0, X/X) contains the underweight coins.
Second, if one, and only one, weighing showed the two sides equal in weight, then the underweight bag is the one whose coins were not weighed during the equal weighting, and on the side with lower weight during the other weighing.
Finally, if both weighings show a discrepancy, the underweight bag is one of the 19 bags whose coins were on the side with lower weight during both weighings. To find which of the 19 this is, divide the difference in weight from the first weighing by the difference in weight from the second weighing. Since each underweight coin weighs the same, the ratio of weight differences is equal to the ratio of coins weighed. Thus, the weight ratio will match the ratio of one of the sets numbers listed in step two...all 19 of which are unique. The bag with that number set contains the underweight coins. For example, if the left pan weighed 10g less during the first weighing, and the right pan weighed six grams less during the second weighing, the underweight bag is the one labeled (5/3, L/R).
If there were more than 81 bags, three weighings would be required. However, using the same procedure, where the ratios of coins in all weighings are unique, a single underweight bag can be found from a total of as many as 1155 bags in only three weighings. In four weighings, one underweight bag can be found in a whopping 13857 bags total.