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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't know how obvious it is, but I wouldn't downbote this. $\endgroup$ – Fimpellizieri Nov 23 '16 at 20:50
  • $\begingroup$ Its not obvious at all $\endgroup$ – J. Don Nov 23 '16 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$ – CurveEnthusiast Nov 23 '16 at 20:54
  • $\begingroup$ That would be very helpful. Thanks $\endgroup$ – J. Don Nov 23 '16 at 20:56
  • $\begingroup$ Added the solution to the answer. $\endgroup$ – CurveEnthusiast Nov 23 '16 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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.