8

I was trying to solve a puzzle but was not able to find any solutions if any one knows the solutions please, share.

"You own a shop of chocolates. You want to give exact number of chocolates (say for orders up to 1000 chocolates) to customers without counting them at the time of giving. You can prefill chocolates in bags by counting them upfront and give appropriate bags (one or many) to fulfill the order. What is the minimum number of bags will you need to satisfy your first order? (Remember you do not know what is the order upfront)"

Nagama Inamdar
  • 103
Neo-coder
  • 181

1 Answers1

7

The answer is to use bags of size $1, 2, 4, 8, 16, 32, 64, 128, 256, 512$. By binary representation, we can satisfy any order with these bags (up to $1023$, not just up to $1000$). This is $10$ bags.

Now suppose we only had $9$ (or less) bags. Then the number of ways we could give out some subset of these bags would be $2^9$ (or less). But there are $1000$ distinct possible orders we need to be able to satisfy, and we can only make at most $2^9 = 512$ different orders using a subset of the bags we prepared. Thus $10$ bags is the minimum number possible.

Caleb Stanford
  • 45,895
  • 1
    If you have 9 bags, with $2,4,\dots,512$ chocolates, you can fill any even order, and, if the customer makes an odd order $2n-1$, you just remove a chocolate from one of the bags you use to make $2n$. You don't need to do any counting to remove a chocolate from a bag. – Gerry Myerson Oct 06 '13 at 08:32
  • But you still have to count when you sell them, when you do the additions. Putting them in bags simply makes the calculations easier. – Viktor Mellgren Oct 06 '13 at 11:49