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!

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}$.

• I don't know how obvious it is, but I wouldn't downbote this. Nov 23, 2016 at 20:50
• Its not obvious at all Nov 23, 2016 at 20:53
• 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. Nov 23, 2016 at 20:54
• That would be very helpful. Thanks Nov 23, 2016 at 20:56
• Added the solution to the answer. Nov 23, 2016 at 21:00

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