|
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 |
|