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\]
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?