Check out some similar questions!

anonymous6 · Mar 5, 2011, 05:00 PM

Hi, I need to solve this proof put I cannot seem to figure it out. I'd really appreciate some help!

If a dollar is 100 cents and coins come in 1, 2, 5, 10, 20, 50 and 100 cents. Suppose that one can make A cents using exactly B coins. Prove that it is possible to make B dollars using exactly A coins

ebaines · Mar 7, 2011, 09:52 AM

The trick here is to notice that that each coin value $V_i$ in cents has a "partner" whose value is $\frac {100}{V_i}$ in cents. There are seven coin values, which we will call $V_0$ through $V_6$ . Hence:

$ V_{6-i}= \frac {100} {V_i} $

So 1 = 100/100, 2 = 100/50, 5 = 100/20, 10 = 100/10, 20 = 100/5, 50 = 100/2, and 100 = 100/1.

When you choose the B coins the value of that set is equal to A:

$ B = \displaystyle \sum _{i=0} ^6 N_i \\ \\ A = \displaystyle \sum _{i=0} ^6 N_i V_i $

Where $N_i$ is the quantity of the "ith" coin value. Now suppose you select another set, but this time let the quantity of each coin value be set to $M_i = N_{6-i} \times V_{6-i}$ . The total quantity of coins is then:

$ \sum M_i\ =\ \displaystyle \sum _{i=0} ^6 N_{6-i} V_{6-i} = \displaystyle \sum _{i=0} ^6 N_i V_i = A. $

And the value of the collection is:

$ \displaystyle \sum _{i=0} ^6 (N_{6-i} \times V_{6-i}) V_i = \ \displaystyle \sum _{i=0} ^6 (N_{6-i} \times \frac {100} {V_i})V_i = 100 \times \displaystyle \sum _{i=0} ^6 N_{6-i} \ = \ 100 \times \displaystyle \sum _{i=0} ^6 N_i\ = \ 100B $

So by choosing the quantities of each coin correctly, you use A coins to get B x 100 cents, or B dollars.

Here's an example: suppose you initially select three 1-cent pieces, two 5-cent pieces and one 10-cent piece. You have:

B = 3 + 2 + 1 = 6 coins
A = 3x1 + 2x5 + 1x10 = 23 cents

You can now select 23 coins to make 6 dollars as follows:

3x1 100-cent pieces, plus 2x5 20-cent pieces, plus 1x10 10-cent pieces. That's 23 coins with a value of 6 dollars.

Hope this helps!

jcaron2 · Mar 8, 2011, 08:19 AM

Nice!