# Dollars and Envelopes

1. Apr 4, 2016

### collinsmark

Here is another riddle inspired by the puzzler on this week's rerun of Car Talk.

I'm going to hand you one thousand dollars, in one-dollar bills. Your job is to put those dollar bills in some number of envelopes, in such a manner that no matter what number of dollars I ask you for you'll hand me the appropriate combination of envelopes.

The question is--what's the smallest number of envelopes, and how much money do you put in each one?
Here are some additional clarifications (to catch the low hanging fruit):
• I may ask you for any number between $0 and$1000 inclusive, with the smallest denomination of one dollar. (I won't ask for $223.65 or anything involving change -- but I might ask for$223 or $224). You need not be concerned with fractional dollars. • You need to hand me the exact amount of dollars, no more, and no less (although it might involve multiple envelopes). • Once the money is in the envelopes, and I ask for a number, no reshuffling of money is allowed (i.e., you cannot redistribute money from one envelope to another). You may only hand me the pre-existing stuffed envelopes. • Initially, you have exactly$1000, in single dollar bills to work with. (You may not add or subtract additional dollar bills from that amount. You many not use your own money that you already have in your pocket, etc.)
• I will only ask you for a number once. And you only have to hand me the appropriate combination of envelopes once.
• You may put different amounts of money in each envelope (although the total must sum to exactly $1000). Examples: • You could put 500 dollars into two envelopes (500 bills in each envelope). That would require only two envelopes. But if I asked you to produce$499 dollars, you wouldn't be able to do it. So this strategy is considered a failure.