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

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