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?
Best Answer
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$.