Challenge of Father to Son

A man told his son that he would give him $1000 if he could accomplish the following task. 

The father gave his son ten envelopes and a thousand dollars, all in one dollar bills. He told his son, "Place the money in the envelopes in such a manner that no matter what number of dollars I ask for, you can give me one or more of the envelopes, containing the exact amount I asked for without having to open any of the envelopes. If you can do this, you will keep the $1000."

When the father asked for a sum of money, the son was able to give him envelopes containing the exact amount of money asked for. 

How did the son distribute the money among the ten envelopes?

THIS is how son accepts the challenge!

Son's Response to the Father's Challenge

What was the challenge?

For a moment, let's suppose father had given $30 to son and provided 5 envelopes and put the same challenge.
----------------------------------------------------------------------------------------------------
Here, use of the binary number system helps in matter.

The son would distribute 15 dollars into 4 envelops like - 

2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8.

Now, for any amount asked between 1 to 15, son can produce some of these 4 envelops wherever 1 is there in envelop column for that particular amount.

For example, if father asks for $10 (Binary - 1010), son would give envelop 4 and 2 (8+2=10).

After putting $15 dollar in 4 envelops, he puts remaining $15 in 5th envelop so that he can cover rest of amount between 16 to 30.

If father asks amount greater than 15 then he would take envelop of $15 first and depending on how much the amount asked is greater than this $15 he would pick some of those 4 envelops.

For example, if father asks for $24, then he picks envelop 5 having $15 and envelops for amount 24 - 15 = 9 (Binary - 1009) i.e. envelop 4 and 1 (8+1=9)  i.e. total of 15 + 9 = 24.

So, what we observe from this is that the number of envelops needed for such arrangement is equal to the number of binary bits needed to represent the amount itself or nearest power of 2 greater than the amount.

In above case, to represent 30 in binary we need 5 bits or nearest power of 2 greater than 30 is 32 which needs 5 bits for representation.

-----------------------------------------------------------------------------

Now, let's turn to the actual challenge where father has asked son to distribute $1000 rightly in 10 envelopes. 

The reason for selecting 10 as a number of envelops is clear now as 1000 needs 10 bits in binary or nearest power of 2 greater than 1000 is 1024 which needs 10 bits for binary representation.

So, the son puts 256, 128, 64, 32, 16, 8, 4, 2, 1 dollars in 9 envelops (envelop numbered as Envelop 9, Envelop 8.........Envelop 1 in order)
 and 1000 - 511 = 489 dollars in 10th envelop.

First 9 envelops will cover amounts from 1 to 511 and for amounts greater than 511 inclusion of 10th envelop having 489 dollars is mandatory.

Again selection of envelops for the amount 511 to 1000 depends on how much the amount exceeds the $489. The binary representation of that difference and selection of envelop accordingly is all that needed.
 
----------------------------------------------------------------------------------------------------

Let's make sure this distribution with couple of examples.

If father asks for amount of $109 (binary - 1101101) then son picks 

Envelop 1($1) + Envelop 3 ($4) + Envelop 4 ($8) + Envelop 6 ($32) + 
Envelop 7 ($64) i.e. having amount = 1 + 4 + 8 + 32 + 64 = 109 dollars.

If father asks for $525 then son gives $489 via Envelop 10 and rest of amount 
530 - 489 = 40 (Binary - 101000) in form of Envelop - 6 ($32) and Envelop 4 ($8).   

----------------------------------------------------------------------------------------------------