The $1,000.00 Cash Distribution Problem

 

How do you divvy up 1,000 one dollar bills into some number of envelopes so that you can, by choosing some subset of those envelopes, make up any sum from $1.00 all the way up to $1,000.00. 

One solution is to use 1,000 envelopes each with $1.00 in it. 

Is there a solution using a smaller number of envelopes, and if so what is the smallest number and how many dollars go into each envelope?

Yes: The minimum number of envelopes is 10 and the number of bills they contain contain is: 489, 256, 128, 64, 32, 16, 8, 4, 2 and 1.

Here is how you can show that these envelopes can be used to make up any number from 1 to 1,000:

Work your way up. You find that with two envelopes you can solve the $3.00 cash distribution problem by putting $2.00 in one envelope and $1.00 in the other envelope. You can make 1, 2 or 3 dollar amounts only using 2 envelopes. 

To make one dollar amount use the envelope with one dollar in it. 
To make two dollars use the envelope with two dollars in it. 
To make three dollars use both the envelope with two dollars in it and the envelope with one dollar in it.

When you add a third envelope in hopes of solving some problem greater than the $3.00 problem you notice a very interesting thing when you choose that envelope to contain one dollar more than the problem you just solved.

In other words putting $4.00 in the next envelope you solve the $4.00 problem plus you still have all your other envelopes which can solve any problem from $1.00 all the way to $3.00.

So now you have just solved the problem all the way from $4.00 up to $7.00 and you also notice that this is the best you can do to solve the $7.00 cash distribution problem.
 
Add to this by choosing $8.00 for the next amount you find you solved all the way up to the $15.00 problem.

Continuing in this way (doubling the money in the next envelope) you find that you get all the way to solving the $511.00 problem with nine envelopes (the last one having $256 in it).

However, if you try to put $512.00 in the next one you actually solve the $1,023.00 problem (and you use more money than you have) so then you find that dropping back to $489.00 in the tenth envelope you get exactly the $1,000.00 solution.

Here is a table that shows this solution in action:
 

Envelope
Number
Envelope
Amount
Amounts That Can Be Created Maximum
Amount
1  $1   $1 $1 
2  $2   $2, $2+$1 $3
3  $4   $4, $4+$1, $4+$2, $4+(3) $7
4  $8   $8, $8+$1, $8+$2, $8+(3) ... $8+(7)  $15
5 $16 $16, $16+$1, $16+$2, $16+(3) ... $16+(15) $31
6 $32 $32, $32+$1, $32+$2, $32+(3) ... $32+(31) $63
7 $64 $64, $64+$1, $64+$2, $64+(3) ... $64+(63) $127
8$128$128, $128+$1, $128+$2, $128+(3) ... $128+(127) $255
9$256$256, $256+$1, $256+$2, $256+(3) ... $256+(255) $511
10$489$489, $489+$1, $489+$2, $489+(3) ... $489+(511)$1000

This Page Last Update Saturday, March 04, 2006 17:03:21 -0500