Link to the Problem
Consider the bags as switches, switching the first bag on indicates that u give away the first bag full of coins. This can be represented as a 10 bit long binary number with which you can represent 0 to 1023 numbers. But here you have only 1000 coins. With 9 bits you can represent numbers from 0 to 511. Put 2^0 = 1 coin into the first bag, 2^1 = 2 coins into the second bag, 2^2 = 4 coins into the third bag, ... so on till you put 2^8 = 256 coins into the 9th bag. With this arrangement you can give away all denominations till (2^10-1) = 511. And you have 489 coins left. Put all of that into the 10th bag and now to represent any number from 512 to 1000 (lets say N) just give away the bag with 489 coins and the combination of bags which equate to (N-489) which will always be less than or equal to 511 (since N <= 1000) and is hence achievable using the combination of other 9 bags!
Hence, the number of coins that you put into the bags are 2^0, 2^1, 2^2, .... , 2^8, 489.
No comments:
Post a Comment