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?

• A. 11
• B. None of these
• C. 13
• D. 12

Hint:

Each bag is either handed out or not. Count how many different totals n bags can make, and compare with the 159 amounts (0 to 158) that must be possible.

Answer 1

The Correct Option is B

Step 1: Find a lower bound:
For each bag we can either hand it out or not, so n bags can make at most \(2^n\) different totals (including the total 0). We need every amount from 0 to 158, which is 159 different totals.
With 7 bags: \(2^7 = 128 < 159\), so 7 bags are not enough.
With 8 bags: \(2^8 = 256 \ge 159\), so 8 bags might be enough.

Step 2: Show that 8 bags really work:
Take the bags 1, 2, 4, 8, 16, 32, 64 and 31. Their total is \(127 + 31 = 158\), as required.
The first seven bags (1, 2, 4, 8, 16, 32, 64) can make every amount from 0 to 127.
Any amount N from 128 to 158 is made by handing out the bag of 31 together with the first-seven-bags amount \(N - 31\), which lies between 97 and 127.
So every amount from 1 to 158 can be given.

Step 3: Compare with the options:
The minimum number of bags is 8. It is not 11, 12 or 13.

Final Answer:
The correct option is (2): None of these (the minimum is 8 bags).