27
$\begingroup$

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.

$\endgroup$
10
  • 4
    $\begingroup$ This is such a cute idea $\endgroup$
    – Laska
    Aug 3, 2023 at 8:51
  • 1
    $\begingroup$ Now if we replace the 20 cent coin with a 25 cent coin, the simple proof is gone, but is it still true or is there a counter example? For example I can pay 25 cent with one coin, and one dollar is 50+25+2*2 + 21*1. $\endgroup$
    – gnasher729
    Aug 3, 2023 at 13:17
  • 2
    $\begingroup$ FYI, for people who want to take a deep dive into the mathematics of coin denominations and making change: Usually when we make change for a given amount, we start with the biggest coin denomination which fits into that amount. Then, we repeat for the remainder. We continue this process until the remainder is zero. That's called the greedy algorithm. Well, it turns out that you can actually construct a crazy set of coin denominations for which the greedy algorithm will not produce the minimum number of coins. $\endgroup$
    – SlowMagic
    Aug 3, 2023 at 15:26
  • 1
    $\begingroup$ (continued) Mathematicians and computer scientists have studied the exact qualities of a set of coin denomination which allows the greedy algorithm to work or not work. See one of many discussions right here on Stack Exchange: stackoverflow.com/questions/13557979/… $\endgroup$
    – SlowMagic
    Aug 3, 2023 at 15:27
  • 2
    $\begingroup$ @gnasher729, With quarters, the issue comes going the other direction. I can pay \$0.05 with 1 coin, so I should be able to pay \$1.00 with 5 coins. The closest I can get is 3 quarters and 2 dimes=\$0.95, or 4 quarters and a penny. $\endgroup$
    – Kaia
    Aug 3, 2023 at 16:43

3 Answers 3

15
$\begingroup$

[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.

$\endgroup$
0
34
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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