Dollars and Envelopes

Credit to CarTalk

Imagine I'm going to give you one thousand dollars, in one-dollar bills. Your job is to put some of those dollar bills in the 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?

• Yes, I stole this one - credit to original given in question source. – Daniel Apr 4 '16 at 15:35
• I made the given credits visible. – manshu Apr 4 '16 at 18:54
• Usually when I credit a source I like to leave it as an html comment so that people can't as easily just go to the website and steal the answer. – Daniel Apr 4 '16 at 20:02

I think binary (with a slight modification for the last envelope) solves this for 10 envelopes max. The envelopes you need contain 1, 2, 4, 8, 16, 32, 64, 128, 256, 489 bills.

Method:

First lay the above envelopes down in reverse order (starting with 489 on the left then reaching 1 on the right).

If the amount asked for is smaller than or equal to 511 then:

Convert that number to binary. Then write the corresponding digits in binary underneath those envelopes (one per envelope), and align the number to the right. Take those envelopes which have a 1 (in binary) under them.

Else, if that number is greater than 511, then take the 489 envelope, and subtract 489 from that number. Then convert that number to binary and execute the steps above.

• Thing is, for that to work, off binary, you'd need 1024 dollar bills. You have exactly 1000 bills... – Tim Couwelier Apr 4 '16 at 15:39
• Oh yeah - you're right. I'll rethink it. Shall I delete this answer for now, or leave it as an idea? – Shuri2060 Apr 4 '16 at 15:40
• actually you need 1023 bills to work. – Marius Apr 4 '16 at 15:41
• Marius - valid point. I was just rushing my comment to avoid Question Asker devoting too much time to an incorrect answer. – Tim Couwelier Apr 4 '16 at 15:41
• I think if I reduce the 512 one by 23, it would work? – Shuri2060 Apr 4 '16 at 15:41

10 envelopes

How?

1, 2, 4, 8, 16, 32, 64, 128, 256, 489

Why?

All the numbers are powers of 2 (except the last one).
Let's take envelope $n\leq8$. You can form any amount up to $2^n$ by the envelopes $1$ to $n$.
Then you can get the amount $2^{n+1}$ from envelope n then start over.
the trick is with envelope $10$.
You can get any amount up to $511$ from envelopes $1$ to $9$.
For amounts from $512$ to $1000$ you just need to take envelope $10$ and the rest will be below 511 so you can still get them from the other envelopes.
side effect, you can get the amounts from $489$ to $511$ in 2 ways.

• 6 isn't a power of 2 – StephenTG Apr 4 '16 at 15:57
• @StephenTG. Sorry. Typo. My brain hears 2,4 automatically says 6. – Marius Apr 4 '16 at 15:59
• @Marius Mine hears 2, 4, and automatically says 8. Maybe I've been programming too much. – Mason Wheeler Apr 4 '16 at 20:20

Following the approach of the other answers, I particularly like the following values.

500, 250, 125, 63, 31, 16, 8, 4, 2, 1

Process the envelopes starting with the highest value. Hand over each envelope whose value is not greater than the balance owing.

• Interesting... Those are almost identical to the available shutter speeds on an "analog" camera... – BobT Apr 5 '16 at 3:14
• Hmmmm, interesting. I would accept this as another correct answer - albeit it's not the one I've been looking for... – Daniel Apr 5 '16 at 3:37