5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Yes, I stole this one - credit to original given in question source. $\endgroup$
    – Daniel
    Apr 4, 2016 at 15:35
  • 3
    $\begingroup$ I made the given credits visible. $\endgroup$
    – manshu
    Apr 4, 2016 at 18:54
  • $\begingroup$ 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. $\endgroup$
    – Daniel
    Apr 4, 2016 at 20:02

3 Answers 3

7
$\begingroup$

Answer:

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.

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

Answer:

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.