wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> The Treasurer's New Bills
        
(Message started by: jeremiahsmith on Dec 2^nd, 2002, 11:02am)

Title: The Treasurer's New Bills
Post by jeremiahsmith on Dec 2^nd, 2002, 11:02am

(I thought of this puzzle just before going to sleep, after messing around with a few bills in my wallet.)

So, Willy Wutang has risen above the three-women, two-condoms scandal, escaped getting STDs, and survived burning isles of flame, and has now succeeded in his toughest challenge: getting political office. Good ol' Willy has become the new Secretary of the Treasury of the US. He's noticed that most people hate fumbling with large amounts of dollar bills in their wallets, and thinks it would be nice if all amounts of money that most people would typically have in their wallet at one time (i.e., less than $100) could be made with a small number of bills. Willy decides that four would be a good number. However, Willy realizes he has a problem: not all numbers under $100 can be made using a maximum of four American bills (which are, for reference, $1, $2, $5, $10, $20, $50, and $100). For example, he can't make $38 with just four bills. So he decides to have new bills made, to facilitate making four-bill amounts. And now he needs your help in deciding what values the new bills should be! He promises that if you help, you get to be on the money. You will need to work according to the following constraints, however (higher numbered constraints have higher priority):

1. The Treasury can only afford so much new printing presses, so you must have four or less new bills.
2. Designing new designs for bills and making new presses will be expensive, so you need to minimize the amount of new bills.
3. The new bills must "cover" as many values as possible from $1 to $100. If there are two numbers that Combination A can't make, and three numbers that Combination B can't make, use Combination A.
4. Willy's research has shown that people prefer smaller-value bills to larger ones when messing with bills. Thus, the average value of the new bills should be as low as possible.

So, what bills should Willy use in his plan?

Other variants are possible:
A) Allow every amount to be made in three bills or less.
B) Coverage (condition 3 above) is more important than minimal bills (condition 2 above).
C) Willy decides that the $2 is a relatively uncommon bill, and decides to ignore it completely during the course of the problem. (Although, if he needs to add a $2 bill, you don't need to count it as a new bill.)
D) The new bills must be multiples of 5. Or they must be even.
E) Let X be the number of bills that each amount must be made from (in the main problem above, X is 4, in variant A, X is 3, etc.) What value of X requires the least amount of bills to FULLY cover $1 to $100? X must require at least one new bill to be made, though; for large enough values of X, you will need to add no new bills and the problem is trivial. (Also, what's the smallest value of X for which you will need to add no bills? I think it's 6.)

I'm sure you all can think of more variants :)

Title: Re: The Treasurer's New Bills
Post by That Don Guy on Dec 4^th, 2002, 12:02pm

If you're limited to four bills total (as opposed to four different kinds of bills, in which case you only really need $1 bills to cover every amount), then there are no more than 15 possible numbers you can "cover" with them (not including zero). You only get 15 different numbers if no number can be made in two different ways (so, for example, you don't have 1, 2, and 3, as you can make 3 with a 3 or a 1 plus a 2). Since "smaller is better", the optimum solution seems to be bills of $1, $2, $4, and $8.

Then again, it depends on the definition of constraint 2's "minimize the amount of new bills". This would imply that you would want larger numbers (i.e. pretty much the opposite of constraint 4), in which case the bills could be $23, $24, $25, and $28 in order to cover 15 different values <= $100.

Title: Re: The Treasurer's New Bills
Post by James Fingas on Dec 4^th, 2002, 12:21pm

Don Guy,

I think you're misinterpreting the problem. We're saying that the number of bills in your wallet is limited to four different bills. In the entire US of A there will be more than four different types of bills.

We currently have bills in the denominations {1,2,5,10,20,50,100}, and we are going to add up to four new denominations, so that a store clerk can make change for any dollar amount from $1 to $100, using both old and new denominations, without ever having to dispense more than 4 bills. For example, if you created the 8-dollar bill, you could make up $38 using $8+$10+$20. Currently, you can't make up $38 without using more than 4 bills ($1+$2+$5+$10+$20).

After Willy is done, there will be up to 11 denominations out there, for 15choose4 = 1365 possible combinations.

Title: Re: The Treasurer's New Bills
Post by Garzahd on Dec 6^th, 2002, 1:50pm

Made a wee little program to brute-force things. Fewer bills than I expected were required:

With the addition of a $34 bill, all sums up to 100 are doable in 4 bills, except for $97 which requires 5.

With the addition of a $33 bill, 75 of the 100 sums are doable in 3 bills. (this is the best that can be done with 1 added bill)

All sums up to 100 are doable in 4 bills with the addition of a $7 and a $19 bill. Second place is a tie between (3,24) and (8,19).

I think part of the reason the bill counts are so low is that we don't use the $2 bill in society as much as would be efficient. Assuming we remove it:

The best 1-bill solution is to add a $13 bill, which gives 90% coverage in 4 bills and 58% coverage in 3 bills.

The best 2-bill solution is (9,23), followed by (7,28), both giving 100% coverage. Interestingly there are only 10 two-bill combinations that give 100% coverage; there are several hundred if the $2 bill is included.

Edit: disabled smileys so (7,28) appears correctly.

Title: Re: The Treasurer's New Bills
Post by Kozo Morimoto on Dec 9^th, 2002, 3:15pm

How about adding a negative integer amount?

I remember reading a sci fi novel where a society used negative amount money - more bills you had, more in debt you were. So when you shopped for groceries, the shop gave you bills as well as your groceries. So the purpose was to try to get rid of as much bills as possible in life. There were even 'beggar' on the street trying to give away bills!

So to get $38, you would have $10 + $20 + (-$2)

Title: Re: The Treasurer's New Bills
Post by That Don Guy on Dec 9^th, 2002, 3:43pm

I think you're misinterpreting the problem. We're saying that the number of bills in your wallet is limited to four different bills. In the entire US of A there will be more than four different types of bills.

We currently have bills in the denominations {1,2,5,10,20,50,100}, and we are going to add up to four new denominations, so that a store clerk can make change for any dollar amount from $1 to $100, using both old and new denominations, without ever having to dispense more than 4 bills. .

Actually, the part I misunderstood was that "new bills" meant "in addition to the existing denominations" - I thought we were replacing the current denominations with the four new ones.