1000 $1 Bills in 10 Envelopes

Date: 12/11/2002 at 04:10:54
From: Kendel
Subject: Word problem

You are given 1000 one dollar bills and 10 envelopes. Put the bills 
into the envelopes in such a way that someone can ask you for any 
amount of money from $1 to $1000 (examples - $532, $619, $88, etc.)
and you can give it to them through a combination of the envelopes.

I am NOT a math person by any means and I'm sure that the answer to 
this problem is painfully obvious; however, I can't get it! I can do 
it with 12 envelopes like this - 400, 300, 100, 100, 40, 30, 20, 10, 
5, 2, 2, 1, but I can't get it down to ten. I'd appreciate a response 
as soon as you have time. 

Thank you, 
Kendel

Date: 12/11/2002 at 10:19:20
From: Doctor Ian
Subject: Re: Word problem

Hi Kendel,

If you can add 23 dollars of your own, then it's easy, since you can
then use each envelope to represent one place value in a binary 
expansion:

  512 256 128 64 32 16 8 4 2 1

Now you can get any number between 1 and 1023, e.g., 

            9   8   7   6   5   4   3   2   1   0
           2   2   2   2   2   2   2   2   2   2 

          512 256 128  64  32  16   8   4   2   1

     $1 =                                       x
  
     $5 =                               x       x

   $143 =           x               x   x   x   x

  $1023 =   x   x   x   x   x   x   x   x   x   x   
 
But if you only have $1000, you can only get 489 into the final 
envelope.  Does this make a difference? 

Well, you can still use the first 9 envelopes to return any amount up
to $511.  So with the final envelope you can get anything between 

  $489 + $1 = $490

and

  $489 + 511 = $1000

So it works fine.  

Does this make sense?

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/