Mathematics Problem Of the Week

Spring 2008

POW #12

Flufferden’s Figgles

Paying amounts in U.S. currency is relatively straightforward and efficient. Assuming whole dollar amounts and bills in denominations of $1, $5, $10 and $20, we simply count out as many $20’s (the largest denomination) as possible, then count the number of $10’s (next largest) in what’s left and so forth until we finish with however many $1’s might be required to get to the desired amount. This method (algorithm) will always use the minimum number of bills to obtain the target value.

Things are more interesting in the country of Flufferden which uses the figgle as its currency. Figgle bills come in denominations 10f, 7f, 6f and 1f.

(a) What is the smallest amount that demonstrates that the U.S. “use as many of the largest bill as possible” algorithm does not work to give the most efficient solution (fewest bills) with amounts in figgles?

(b) What is the most efficient way for a Flufferdenian to pay 26 figgles?

(c) What is the most efficient way for a Flufferdenian to pay 35 figgles?

(d) Describe as general method or algorithm as you can for determining how to pay n figgles with the fewest number of figgle bills. Hint: Start with small amounts and look for patterns.

Due Friday, April 25^th at Noon.

Solutions should be submitted to Dr. R. Lock's mailbox in the Math/CS/Stat office or sent via e-mail to rlock@stlawu.edu.