A probability problem by saurabh suman
Anil wants to divide Rs 100 into a number of bags so that one can ask for any amount b/w Rs 1 to 100, he can give the proper amount by giving certain number of these bags without taking out the amount from them. What is the minimum number of bags he will require if each bag has whole number of rupees?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
There must be at least 7 bags in order to have at least 1 0 0 possible sums, as this would give us a maximum of 2 7 − 1 = 1 2 7 different (positive) sums. (If there were only 6 bags then there would only be a maximum of 2 6 − 1 = 6 3 different sums.)
Now that we've established an absolute minimum, we need to see if this minimum can be achieved. This can be done with bags holding 1 , 2 , 4 , 8 , 1 6 , 3 2 and 3 7 rupees, respectively.
Thus the answer is indeed 7 .