Dollars and Envelopes

Apr 02, 2016

RAY: I'm going to hand 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.

TOM: There must be more to it, because I could just use a thousand envelopes.

RAY: There is more. The question is--what's the smallest number of envelopes, and how much money do you put in each one?

RAY: In the first nine envelopes, you're going to put one dollar, 2 dollars, then 4, 8, 16, 32, 64,128, and 256. That's nine envelopes. If you add all those up, that's 511 dollars.
So if I ask you for any amount up to 511 dollars, you would give me some combination of those envelopes, and if I asked you for 511, you’d give me all of them. So, what do you put in the next envelope?

TOM: Everything else.

RAY: Exactly. 489 bucks. And if you do that, you can give me any amount of money that I ask for. For example, if I ask for 671 dollars, you would give me the envelope that's 489 dollars, plus you'd give me another 182 dollars. You could do that combination with the other envelopes. So who's our winner?

TOM: Congratulations to Jay Mackerell from San Juan Capistrano, California!

Get the Car Talk Newsletter