# Problem of the Week Problem E and Solution Coin Combinations

## Problem

In Canada, a $$\2$$ coin is called a toonie, a $$\1$$ coin is called a loonie, and a $$25$$¢ coin is called a quarter. Four quarters have a value of $$\1$$.

How many different combinations of toonies, loonies, and/or quarters have a total value of $$\100$$?

Note: In solving this problem, it may be helpful to use the fact that the sum of the first $$n$$ positive integers is equal to $$\tfrac{n(n+1)}{2}$$. That is, $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ For example, the sum of the first $$10$$ positive integers is $1 + 2+3+4+5+6+7+8+9+10 = \frac{10(10+1)}{2} = \frac{10(11)}{2}= 55$

## Solution

We will break the solution into cases based on the number of $$\2$$ coins used. For each case, we will count the number of possibilities for the number of $$\1$$ and $$25$$¢ coins.

The maximum number of $$\2$$ coins we can use is $$50$$, since $$\2\times 50 = \100$$. If we use $$50$$ $$\2$$ coins, then we do not need any $$\1$$ or $$25$$¢ coins. Therefore, there is only one way to make a total of $$\100$$ if there are $$50$$ $$\2$$ coins.

Suppose we use $$49$$ $$\2$$ coins. Since $$\2\times 49 = \98$$, to reach a total of $$\100$$, we would need two $$\1$$ and no $$25$$¢ coins, or one $$\1$$ and four $$25$$¢ coins, or no $$\1$$ and eight $$25$$¢ coins. Therefore, there are $$3$$ different ways to make a total of $$\100$$ if we use $$49$$ $$\2$$ coins.

Suppose we use $$48$$ $$\2$$ coins. Since $$\2\times 48 = \96$$, to reach a total of $$\100$$, we would need four $$\1$$ and no $$25$$¢ coins, or three $$\1$$ and four $$25$$¢ coins, or two $$\1$$ and eight $$25$$¢ coins, or one $$\1$$ and twelve $$25$$¢ coins, or no $$\1$$ and sixteen $$25$$¢ coins. Therefore, there are $$5$$ different ways to make a total of $$\100$$ if we use $$48$$ $$\2$$ coins.

We start to see a pattern. When we reduce the number of $$\2$$ coins by one, the number of possible combinations using that many $$\2$$ coins increases by $$2$$. This is because there are $$2$$ more options for the number of $$\1$$ coins we can use. Thus, when we use $$47$$ $$\2$$ coins, there are $$7$$ possible ways to make a total of $$\100$$. When we use $$46$$ $$\2$$ coins, there are $$9$$ possible ways to make a total of \$100, and so on. When we use $$1$$ $$\2$$ coin, there are $$99$$ different ways to make the difference of $$\98$$ (because you can use $$0$$ to $$98$$ $$\1$$ coins). When we don’t use any $$\2$$ coins, there are $$101$$ different ways to make a total of $$\100$$ (because you can use $$0$$ to $$100$$ $$\1$$ coins). Thus, the number of different combinations of coins that have a total value of $$\100$$ is $1 + 3 + 5 + 7 + 9 + \cdots + 99 + 101$ Adding and subtracting the even numbers from $$2$$ to $$100$$, we get $1 + 2 +3 +4+ 5 +6+7 +8+ 9 + \cdots +98+ 99 +100+ 101 - (2 + 4+6+8+\cdots +98 +100)$ Factoring out a factor of $$2$$ from the subtracted even numbers, we get $(1 + 2 +3 + \cdots + 100+101) - 2 (1+2+3+4+\cdots +50)$ We can then use the formula for the sum of the first $$n$$ positive integers to find that this expression is equal to $\frac{101(102)}{2} - 2\left(\frac{50(51)}{2}\right) = 101(51) - 50(51)=2601$ Therefore, there are $$2601$$ different combinations of toonies, loonies, and/or quarters that have a total value of $$\100$$.

Extension:

Let’s look at the end of the previous computation another way. \begin{aligned} 1 + 3 + 5 + 7 + 9 + \cdots + 99 + 101 &= \frac{101(102)}{2} - 2\left(\frac{50(51)}{2}\right) \\ &= 101(51) - 50(51) \\ &=51(101-50) \\ &=51(51)\\ &=51^2 \end{aligned} How many odd integers are in the list from $$1$$ to $$101$$? From $$1$$ to $$101$$, there are $$101$$ integers. This list contains the even integers, from $$2$$ to $$100$$, which are $$50$$ in total. Therefore, there are $$101-50=51$$ odd integers from $$1$$ to $$101$$.

Is it a coincidence that the sum of the first $$51$$ odd positive integers is equal to $$51^2$$? Is the sum of the first $$1000$$ odd positive integers equal to $$1000^2$$? Is the sum of the first $$n$$ odd positive integers equal to $$n^2$$?

We will develop a formula for the sum of the first $$n$$ odd positive integers.

We saw in the problem statement that the sum of the first $$n$$ positive integers is $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ Every odd positive integer can be written in the form $$2n-1$$, where $$n$$ is an integer $$\ge 1$$. When $$n=1,\ 2n-1=2(1)-1=1$$; when $$n=2,\ 2n-1=2(2)-1=3$$, and so on. So the 51st odd positive integer is $$2(51)-1=101$$, as we determined above. The $$n$$th odd positive integer is $$2n-1$$. Let’s consider the sum of the first $$n$$ odd positive integers. That is, $1+3+5+7+\cdots +(2n-3)+(2n-1)$ Adding and subtracting the even numbers from $$2$$ to $$2n$$, we get \begin{aligned} &1 + 2 + 3 + 4 + 5 +\cdots + (2n-3) +(2n-2)+(2n-1) +2n - (2+4+6 + \cdots +(2n-2) + 2n)\\ &=(1 + 2 + 3 + 4 +\cdots + 2n) - (2+4+6+8 + \cdots +(2n-2) + 2n) \end{aligned} Factoring out a $$2$$ from the subtracted even numbers, we get $(1 + 2 + 3 + 4 +\cdots + 2n) - 2(1 + 2 + 3 + \cdots + n)$ We can then use the formula for the sum of the first $$n$$ positive integers to find that this expression is equal to \begin{aligned} \frac{2n(2n+1)}{2} - 2\left(\frac{n(n+1)}{2}\right)&= n(2n+1) - n(n+1)\\ &= 2n^2 + n - n^2 -n\\ &= n^2 \end{aligned} Therefore, the sum of the first $$n$$ odd positive integers is equal to $$n^2$$.

For Further Thought: Can you develop a formula for the sum of the first $$n$$ even positive integers?