# Proof of coin and bag problem

There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Identify the bags with 11 coins.

I can solve the problem by using the fact that sum of odd number and even number is odd number

$$x_1+2x_2+4x_3+8x_4+16x_5=323$$ $$odd+even=odd$$ hence $$x1=11$$ $$2x_2+4x_3+8x_4+16x_5=323-11=312$$ dividing by 2

$$x_2+2x_3+4x_4+8x_5=312/2=156$$ $$even + even=even$$ hence $$x2=10$$ similarly continuing ,will get all weights of coin

I found this method very randomly.

I don't have logical reason for dividing by 2 step after each iteration?

is there any better method? what is the reasoning behind this method? is there any recursion happening? how can we prove that this method work?

• Your method works... because it's actually doing the conversion to base 2 the hard way. However, imagine the coins were either 9 gm or 11 gm; the problem could be stated in a similar way, and your approach wouldn't work anymore. There is a direct way - no recursion needed - as I put in my Answer. – mathguy May 24 '16 at 20:03
• can you please explain "conversion to base 2 hard way"? – arjun2_0 May 25 '16 at 3:50

## 1 Answer

First find out how many of the 31 coins (1 + 2 + 4 + 8 + 16) weigh 11 gm. You will find there are 13 of them. Then think of how you can write 13 as a sum of powers of 2 - this is "writing 13 in base 2". Answer, 8 + 4 + 1. So the coins that came from bags 1, 2 and 4 weigh 11 gm each, and the others 10 gm each.

• using this method,we have enumerate all possible way for sum of power of 2. is there any mathematical way of calculating the answer? – arjun2_0 May 25 '16 at 3:39
• Yes, converting from base 10 to base 2. Do you know what that means? You either studied that or you didn't (or, not yet). – mathguy May 25 '16 at 11:18
• i know base conversion.can you explain why my method works? – arjun2_0 May 25 '16 at 11:53