Solve Car Talk's "Dollars and Envelopes" Riddle

[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.
• You could put each $1 bill into its own envelope. But that would require a whopping 1000 envelopes. Your goal is to use as few envelopes as possible. (And yes, there is a way to use fewer than 1000 envelopes.)

Here is a link to the original Car Talk puzzler question:
http://www.cartalk.com/content/dollars-and-envelopes?question

And if you'd rather listen to the original audio, here is a link for that too:
http://d2ozqge6bst39m.cloudfront.net/CT161408.mp3

Edit: Put answers in spoiler tags please.

 

[Hornbein]

Spoiler

Ten envelopes would do it. Powers of two.

 

[collinsmark]

I've edited the the original post to suggest that answers be given in spoiler tags.

Spoiler

Ten envelopes would do it. Powers of two.

Spoiler

I believe you are essentially correct, but you'll have to be slightly more specific since 1000 is not a power of 2.

 

[Ibix]

The number of envelopes for my current best:

Spoiler

13

My current best solution:

Spoiler

300+300+200+100
30+30+20+10
3+3+2+1
1

You can do any multiple of 100 with the first row, then use the second row to add any two digit multiple of 10, and the third to add any single digit number and that gets you up to 999. The last 1 gets you the 1000.

You can also use the same basic strategy with 4, 2, 2, 1 instead of 3, 3, 2, 1. That makes me question if this is optimal.

How am I doing?

 

[collinsmark]

The number of envelopes for my current best:

Spoiler

13

My current best solution:

Spoiler

300+300+200+100
30+30+20+10
3+3+2+1
1

You can do any multiple of 100 with the first row, then use the second row to add any two digit multiple of 10, and the third to add any single digit number and that gets you up to 999. The last 1 gets you the 1000.

You can also use the same basic strategy with 4, 2, 2, 1 instead of 3, 3, 2, 1. That makes me question if this is optimal.

How am I doing?

Spoiler

I have a number that is less than 13, for fewest number of envelopes. But keep working on it!

 

[zoobyshoe]

Spoiler

I get 12.
1,2,2,5,
10,10,20,50
100,100,200,500

 

[Ibix]

New number of envelopes:

Spoiler

10

The corresponding solution is

Spoiler

1, 2, 4, 8, 16, 32, 64, 128, 256, 489
Hopefully I don't need to explain how the first nine give you all numbers up to 511. By adding the 489 envelope I can do 489 - 1000. Again, there seem to be multiple solutions since you have some freedom to choose where to "break" the doubling - for example 1, 2, 4, 8, 16, 32, 62, 125, 250, 500.

 

[collinsmark]

New number of envelopes:

Spoiler

10

The corresponding solution is

Spoiler

1, 2, 4, 8, 16, 32, 64, 128, 256, 489
Hopefully I don't need to explain how the first nine give you all numbers up to 511. By adding the 489 envelope I can do 489 - 1000. Again, there seem to be multiple solutions since you have some freedom to choose where to "break" the doubling - for example 1, 2, 4, 8, 16, 32, 62, 125, 250, 500.

I think that's correct.

Spoiler

That's the answer that I have. I'm pretty sure it's right. (10 envelopes minimum, with 1, 2, 4, 8, 16, 32, 64, 128, 256, 489 as one solution.)

 

[mfb]

I like the last solution by Ibix as it has many round numbers. There are many similar solutions.

Here is a proof that its number of envelopes is optimal:

Spoiler

9 envelopes give you at most 2⁹=512 different sets of envelopes you can hand over, but you have to be able to make up to 1001 different sets.

 

[Kevin McHugh]

We did problems of this sort in QMB in grad school. They were called minimax problems, and you had to solve them for various constraints.

 

[mfb]

Follow-up puzzle: You have a set of envelopes with money in it, no two envelopes have the same amount in them. Someone else has the same set of envelopes. You can pay that person every amount from $0 to $2000 inclusive, you can get change from the other person. What is the minimal number of envelopes you have to have in order to make that possible?