0
$\begingroup$

I can think of examples but I cannot generalize the proof

Suppose you have a currency that has coins to represent 1 cent, 2 cents, 5 cents, 10 cents, 20 cents, 50 cents and 1 dollar. Also suppose you can pay A cents with B coins. Prove that you can pay B dollars with A coins.

Thanks!

$\endgroup$

2 Answers 2

2
$\begingroup$

Since we can pay $A$ cents with $B$ coins, there are non-negative integers $b_1,b_2,b_5,b_{10},b_{20},b_{50}$ and $b_{100}$ such that \begin{align*} A &= b_1+2b_2+\ldots+100b_{100}, \\ B &= b_1+b_2+\ldots+b_{100}. \end{align*} We can pay $B$ dollars with $A$ coins if and only if there are non-negative integers $a_1,a_2,a_5,a_{10},a_{20},a_{50}$ and $a_{100}$ such that \begin{align*} A &= a_1+a_2+\ldots+a_{100}, \\ 100B &= a_1+2a_2+\ldots+100a_{100}. \end{align*} Hence, we can pay $A$ cents with $B$ coins and pay $B$ dollars with $A$ coins if and only if, there are non-negative integers $a_1,a_2,a_5,a_{10},a_{20},a_{50}$ and $a_{100}$ such that \begin{align*} a_1+2a_2+\ldots+100a_{100} &= 100\left(b_1+b_2+\ldots+b_{100}\right), \\ a_1+a_2+\ldots+a_{100} &= b_1+2b_2+\ldots+100b_{100}. \end{align*} Take $a_{100}=b_1$, $a_{50}=2b_2$, $a_{20}=5b_5$, $a_{10}=10b_{10}$, $a_5=20b_{20}$, $a_2=50b_{50}$ and $a_1=100b_{100}$.

$\endgroup$
5
  • $\begingroup$ I don't know how obvious it is, but I wouldn't downbote this. $\endgroup$ Nov 23, 2016 at 20:50
  • $\begingroup$ Its not obvious at all $\endgroup$
    – J. Don
    Nov 23, 2016 at 20:53
  • $\begingroup$ Oh, perhaps it's unfortunately phrased. This is where I noticed a solution, and so was done. I didn't want to spell it out yet, but if you prefer that I will add the answer. $\endgroup$ Nov 23, 2016 at 20:54
  • $\begingroup$ That would be very helpful. Thanks $\endgroup$
    – J. Don
    Nov 23, 2016 at 20:56
  • $\begingroup$ Added the solution to the answer. $\endgroup$ Nov 23, 2016 at 21:00
0
$\begingroup$

I wanted to solve this myself for my own satisfaction, I took a slightly different approach but I thought I'd add it as it's a little different, but it boils down to the same as the other answer.

$B$ coins make $A$ cents, so $\sum n_i c_i = A$ where $n_i$ is the amount of coin $c_i$ (given in the listed order above so 1 cent is $c_1$ and 20 cents is $c_5$) and $\sum n_i = B$.

$\$B = 100B \text{ cents} = \sum 100 n_i = \sum n_i c_i \cdot 100\frac1{c_i}$.

Notice that $100 \frac1{c_i}$ is the coin from the opposite end of the list i.e. for 2 cents, $\frac1{2}\cdot 100 = 50$ cents.

Just to confirm, expanding the last sum gives

$$ \$B =n_1 c_1 \cdot \left(100 \frac1{c_1}\right) + n_2 c_2 \cdot \left(100 \frac1{c_2}\right) + \ldots + n_7 c_7 \cdot \left(100 \frac1{c_7}\right) $$

so we have $\sum n_i c_i = A$ coins

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .