Number of bags such that any amount required between Re 1 and Rs. 158 can be given by handing out a certain number of bags without opening them.

Question

Ashish is given Rs. 158 in one-rupee denominations. He has been asked to allocate them into a number of bags such that any amount required between Re 1 and Rs. 158 can be given by handing out a certain number of bags without opening them. What is the minimum number of bags required?

I have applied brute force method to get the number is eight.

79 , 40 , 20 , 10 , 5 , 2 , 1 , 1

But how to prove that eight is the least number of bags. I think there is a bigger , deeper concept behind it. Can anyone please explain me how it is the least number of bags and if there is any number theory concept behind it?

Answer 1

If you have $n$ bags, then there are $2^n$ different combinations of bags that you can hand out (including handing out 0 bags). Some combinations of bags might total the same amount of money, so with $n$ bags, you can hand out at most $2^n$ different money amounts (including 0).

You need to be able to hand out any money amount between $1$ and $158$; this will be impossible to do with $n$ bags when $2^n < 159$.

Answer 2

Nice problem. I don't think the answer is unique. What about eight bags filled with these denominations?:

$\{1,2,4,8,16,32,64,31\}$

By considering the binary expansion of the number of rupees we want, the first seven bags allow any number between 1 and 127. To get larger numbers (between 128 and 158), include 31 and the needed other bags to get there.