Cash and Envelopes

Logic Level 4

Alice wants to buy Bob’s painting, knowing only that it costs no more than $100,000 and that the price will be an exact dollar figure (e.g. not $13.35).

Bob insists that he only accepts cash, so Alice goes out to the bank and collects $100,000. As Alice doesn’t want to risk getting mugged, she devises a plan:

She places her money in 17 sealed envelopes, numbered accordingly (i.e. they increase in value). The banknotes are distributed in such a way that no matter what price Bob asks, Alice can pay Bob exactly without having to open an envelope.

It is assumed that each envelope contains the least possible number of bills available in US currency (e.g. a fifty-dollar-bill instead of 5 ten-dollar-bills).

When Alice meets Bob, she is told that the painting costs $31721. She pays with 11 envelopes.

With how many one-dollar-bills must Alice pay?

(Remember the US Dollar Bills are $1, $2, $5, $10, $20, $50, $100)

11 1 286 6 0 285

2 solutions

Tran Hieu
Dec 10, 2015

If and In order to be able to pay any sum, the envelopes value should be in increasing multiple of 2, e.g. 1; 2; 4; 8... (with the exception of last envelope which is $100,000 minus the rest).

We can convert 31721 to binary and we got 111101111101001, which mean Alice use the envelope with values 1, 8, 32, 64, 128, 256, 512, 2048, 4096, 8192, 16384.

Now because we only need to count the $1 bill, and it is easy to see that if the envelope value ends with 1, 6, 8 then there is one $1 bill in that envelope, otherwise it haven't got $1 bill (ends with 3 also have $1 bill, but none of the envelope have this value).

So we got envelope 1, 8, 128, 256, 2048, 4096, which equal to six $1 bills

I never thought about converting the price into binary. That is very clever.

Luca Righetti - 5 years, 6 months ago

Luca Righetti
Dec 10, 2015

In order to be able to pay any possible sum, Alice must use the following rule for the first 16 envelopes:

(Let X be the number of the envelope and Y equal the ‘cash value’) Y=2^(X-1)

Hence we know that the first 16 envelopes contain $1, $2, $4, $8, $16, $32, $64, $128, $256, $512, $1024, $2048, $4096, $8192, $16384 and $32768. As the total is $100,000, we know the last envelope (#17) contains $34465.

With Alice having to pay $31721, we can work out the envelopes as follows:

(##) $ in envelope: $ left assign (15) 16384: 15337

(14) 08192: 07145

(13) 04096: 03049

(12) 02048: 01001

(10) 00512: 00489

(09) 00256: 00233

(08) 00128: 00105

(07) 00064: 00041

(06) 00032: 00009

(04) 00008: 00001

(01) 00001: 00000

Now, we need to find out how many one-dollar-bills are in each selected envelope. We do this by tabulating how many bills compromise each value using a very similar method:

e.g. for Envelope #15 ($16384)

Dollar Bill | Max Amount | Left to pay

$100 bills | 163 | $84

$050 bills | 001 | $34

$020 bills | 001 | $14

$010 bills | 001 | $04

$005 bills | 000 | $04

$002 bills | 002 | $00

$001 bills | 000 | $00

We repeat this for all the envelopes and then finally add all the ‘max amount’ values for the one-dollar-bills. This will give us the equation: 0+0+1+1+0+1+1+0+0+1+1 = 6

Moderator note:

Right. As you've already known, converting the number to binary is much quicker.

Can you explain why we use powers of 2 to solve this problem? What is the reasoning behind it?

It seems that there are several configuration for envelopes.

For example if we have to distribute $10 for 4 envelope we can do it in at least two ways: 10=1+2+4+3=1+2+5+2.

In our case we have to split $100000 into 17 parts. Maybe it can be done in such way: $2^0, 2^1, ..., 2^{14}, 50000-(2^{15}-1), 50000$ .

Of course there are other configurations, so answer may be ambiguious.

Alex Alex - 5 years, 6 months ago

Cash and Envelopes

2 solutions

Moderator note:

0 pending reports