Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Dollars and Envelopes

  1. Apr 4, 2016 #1

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

    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: Apr 4, 2016
  2. jcsd
  3. Apr 4, 2016 #2
    Ten envelopes would do it. Powers of two.
     
    Last edited: Apr 4, 2016
  4. Apr 4, 2016 #3

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

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

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

    Ibix

    User Avatar
    Science Advisor

    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?
     
  6. Apr 5, 2016 #4

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

    I have a number that is less than 13, for fewest number of envelopes. But keep working on it!
     
  7. Apr 5, 2016 #5
    I get 12.
    1,2,2,5,
    10,10,20,50
    100,100,200,500
     
  8. Apr 5, 2016 #6

    Ibix

    User Avatar
    Science Advisor

    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.
     
  9. Apr 5, 2016 #7

    collinsmark

    User Avatar
    Homework Helper
    Gold Member

    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.)
     
  10. Apr 7, 2016 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  11. Apr 7, 2016 #9
    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.
     
  12. Apr 7, 2016 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Dollars and Envelopes
  1. Missing Dollar (Replies: 2)

  2. Green Envelopes (Replies: 10)

  3. Dollars and Cents (Replies: 31)

  4. Canadian dollar (Replies: 11)

  5. A trillion dollars (Replies: 29)

Loading...