If A cents can be paid with B coins then prove that B dollars can be paid with A coins

Question

Looking for an intuitive solution to the following problem:

In a certain country the following coins are in circulation: 1 cent, 2 cents, 5 cents, 10 cents, 20 cents, 50 cents, and 1 dollar. It is known that you can pay A cents with B coins. Prove that you can pay B dollars with A coins.

This is a problem from the book, Mathematical circles, a Russian experience by Fomin and other authors.

Answer 1

[An attempt to make an intuitive answer]

If we have one coin worth X cents, we can replace it with X coins worth one dollar. (1¢: 1x\$1, 2¢: 2x50¢, 5¢: 5x20¢, 10¢: 10x10¢, 20¢: 20x5¢, 50¢: 50x2¢, \$1: 100x1¢). We can do this for each of the B coins summing to A cents, and will then have A coins summing to B dollars.

[Based heavily on the other answers by Jaap and Plop]

Chat asks what happens if we swap the 20c coin for a 25c coin.

gnasher729 points out that the 25c coin can be replaced with 50 + 25 + 2x2 + 21x1

Kaia asks about the 5c coin, counterpart to the now-lost 20c coin. It can be replaced with 50+25+5+10+10.

so it is less obvious that it holds, but is still true.

Answer 2

The reason it works for this set of coins is that

for every coin of value $v$ cents, there is also a coin of value $\frac{100}v$ cents.

Using this fact, you can look at each coin value individually:

$k$ coins of value $v$ cents make $kv$ cents.
$kv$ coins of value $\frac{100}v$ cents make $k$ dollars, because $kv\cdot\frac{100}v=100k$ cents.

Since the statement is true for each coin value, it is also true for any combination of these coin values. More specifically:

Suppose we have
$c + d + e + f + g + h + i = B$
$c\cdot 1 + d\cdot 2 + e\cdot 5 + f\cdot 10 + g\cdot 20 + h\cdot 50 + i\cdot 100 = A$
where the first equation is the number of coins and the second denotes their total value.
You can multiply the first equation by $100$ to get the following:
$c\cdot 100 + 2d\cdot 50 + 5e\cdot 20 + 10f\cdot 10 + 20g\cdot 5 + 50h\cdot 2 + 100i\cdot 1 = 100\cdot B$
$c + 2d + 5e + 10f + 20g + 50h + 100i = A$
Here you can interpret the second equation as the number of coins and the first as their corresponding total value.

Answer 3

I do it by induction on $B$, i.e. let's name $P(B)$ the sentence: "for all $A$, if $A$ cents can be paid with $B$ coins, then $B$ dollars can be paid with $A$ coins". I will prove $\forall B,\ P(B)$ by induction.

For $B = 0$, it is trivial.

Assume it is true for some $B$. Let $A$ be a cent amount that can be paid with $B+1$ coins. Let $v$ be the value of the last coin. If $v=1$, then $A-1$ can be paid with $B$ coins, so, by assumption, $B$ dollars can be paid with $A-1$ coins. We just add a one dollar coin and we can pay $B+1$ dollars with $A$ coins. If $v=2$, we do the same, but we add two fifty cent coins; if $v=5$, we do the same, but we add five twenty cent coins, etc. Precisely, for any value $v$ of the last coin, we can pay one dollar with $v$ coins, because $\frac{100}{v}$ is the value of a coin too.