Solve Car Talk's "Dollars and Envelopes" Riddle

  • Thread starter collinsmark
  • Start date
In summary, the conversation discusses a riddle inspired by a puzzler on Car Talk. The riddle involves putting $1000 in single dollar bills into envelopes in a way that allows for any amount to be requested and given without reshuffling the money. The question is how to use the fewest number of envelopes and what amount of money to put in each one. The solution involves using a varying number of envelopes with different amounts of money in each one, and the optimal solution uses round numbers. A follow-up puzzle is also posed involving using a set of envelopes with different amounts of money to pay any amount from $0 to $2000 with change.
  • #1
collinsmark
Homework Helper
Gold Member
3,391
2,666
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. o0)
 
Last edited:
  • Like
Likes Pepper Mint, Samy_A and Ibix
Physics news on Phys.org
  • #2
Ten envelopes would do it. Powers of two.
 
Last edited:
  • Like
Likes Borg and collinsmark
  • #3
I've edited the the original post to suggest that answers be given in spoiler tags. :smile:

Hornbein said:
Ten envelopes would do it. Powers of two.

I believe you are essentially correct, but you'll have to be slightly more specific since 1000 is not a power of 2.
 
  • #4
The number of envelopes for my current best:
13
My current best solution:
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?
 
  • Like
Likes collinsmark
  • #5
Ibix said:
The number of envelopes for my current best:
13
My current best solution:
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?
I have a number that is less than 13, for fewest number of envelopes. But keep working on it!
 
  • #6
I get 12.
1,2,2,5,
10,10,20,50
100,100,200,500
 
  • Like
Likes collinsmark
  • #7
New number of envelopes:
10
The corresponding solution is
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.
 
  • Like
Likes Pepper Mint, DrClaude, collinsmark and 1 other person
  • #8
Ibix said:
New number of envelopes:
10
The corresponding solution is
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. :smile:

That's the answer that I have. I'm pretty sure it's right. :smile: (10 envelopes minimum, with 1, 2, 4, 8, 16, 32, 64, 128, 256, 489 as one solution.)
 
  • #9
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:
9 envelopes give you at most 29=512 different sets of envelopes you can hand over, but you have to be able to make up to 1001 different sets.
 
  • #10
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.
 
  • #11
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?
 

Related to Solve Car Talk's "Dollars and Envelopes" Riddle

What is the "Dollars and Envelopes" riddle?

The "Dollars and Envelopes" riddle is a logic puzzle that was featured on the popular radio show "Car Talk". It involves a scenario where two people are given envelopes with different amounts of money and must use logic to figure out who has the larger amount.

What are the rules of the "Dollars and Envelopes" riddle?

The rules of the "Dollars and Envelopes" riddle are as follows:

  • Two people, A and B, are given envelopes with different amounts of money.
  • Person A is told that the total amount of money in the two envelopes is $100.
  • Person B is told that one envelope contains twice the amount of the other envelope.
  • Person A is given the option to switch envelopes with Person B.
  • Person B is given the option to switch envelopes with Person A.
  • Both people are told that they can only make one switch.
  • The goal is to end up with the envelope containing the larger amount of money.

What is the solution to the "Dollars and Envelopes" riddle?

The solution to the "Dollars and Envelopes" riddle involves using logic to determine the possible scenarios and making the best decision based on those scenarios. The optimal solution is for Person A to switch envelopes if they are given the option, as this guarantees that they will end up with the larger amount of money. If Person A is not given the option to switch, then they should keep their original envelope.

Are there any variations of the "Dollars and Envelopes" riddle?

Yes, there are several variations of the "Dollars and Envelopes" riddle that involve different amounts of money or different rules for switching envelopes. Some variations also involve more than two people and multiple rounds of switching envelopes.

Why is the "Dollars and Envelopes" riddle considered a logic puzzle?

The "Dollars and Envelopes" riddle is considered a logic puzzle because it requires using logical reasoning and deduction to determine the best course of action. It also involves thinking through all possible scenarios and making decisions based on those scenarios.

Similar threads

Replies
26
Views
959
  • General Discussion
2
Replies
46
Views
3K
Replies
28
Views
2K
  • Math Proof Training and Practice
Replies
5
Views
3K
Replies
35
Views
4K
  • Sci-Fi Writing and World Building
Replies
2
Views
2K
  • General Math
Replies
3
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
  • Precalculus Mathematics Homework Help
Replies
13
Views
3K
Back
Top