April 2026
This month’s Problem of the Month centres around a well-known problem in computer science and optimisation known as the change-making problem. The questions in the POTM are inspired by, and closely follow, the results and arguments in the 1994 theoretical computer science paper Optimal bounds for the change-making problem, by Dexter Kozen and Shmuel Zaks.
I claim that the least number of items needed is three, and that is obtained by using one \(\$2\), one \(\$5\), and one \(\$100\). This collection of denominations is an example of obtaining \(\$107\) using three items, so we need to rule out the possibility that it can be done with one or two items.
One item is not possible since \(\$107\) is not an available denomination.
Since all denominations except for \(\$1\) and \(\$2\) are a multiple of five, we cannot obtain \(\$107\) without using some \(\$1\)s or \(\$2\)s. None of two \(\$1\)s, two \(\$2\)s, or one \(\$1\) and one \(\$2\) amounts to \(\$107\). Since \(\$106\) is not a denomination in the Canadian currency, \(\$107\) cannot be obtained from two items by using exactly one \(\$1\). Since \(\$105\) is not an available denomination, \(\$107\) cannot be obtained from two items by using exactly one \(\$2\).
We have ruled out the possibility that \(\$107\) can be obtained by using only two items.
Since \(37\) is not a denomination, it cannot be obtained with one note.
Since \(37\) is odd, it cannot be obtained with two of the same note. The possible totals obtainable by taking two distinct notes are \(6\), \(11\), \(19\), \(31\), \(15\), \(23\), \(35\), \(28\), \(40\), and \(48\). None of these are equal to \(37\) and so \(37\) cannot be obtained with two notes.
Let \(t > 2\) be an integer. I claim that for the denomination set \((1,t,2t-2)\), the value \(2t\) is the smallest sneaky value.
To see this, first note that \(G(2t) = (2,0,1)\) and so \(|G(t)| = 3\). However, \((0,2,0)\) is a realisation of \(2t\) using only two items. Therefore \(|G(2t)| > E(2t)\) and \(2t\) is indeed a sneaky value. We need to show now that if \(v < 2t\), it is not a sneaky value. We will do this by proving something a little more general:
Claim: For a denomination set \((d_1,d_2,\ldots,d_k)\), if \(v < d_3 + 2\), then \(v\) is not a sneaky value.
Proving the claim will prove that \(2t\) is the smallest sneaky value for the denomination set \((1,t,2t-2)\).
Proof of the claim. Let’s start from the largest values of \(v\). Suppose \(v = d_3 + 1\). If \(d_4 = d_3 + 1\), then certainly \(E(v) = |G(v)| = 1\) so \(v\) is not sneaky. On the other hand, if \(v\) is not in the denomination set, it cannot be obtained with one item, so \(E(v) \geq 2\). Also, \(G(v) = (1,0,1,0,\ldots,0)\) so it must be the case that \(E(v) = 2 = |G(v)|\) and thus \(v\) is not a sneaky value.
If \(v = d_3\), then certainly \(E(v) = |G(v)| = 1\) and it is not a sneaky value.
If \(v < d_3\), then only the denominations \(1\) and \(d_2\) can be used in any realisation of \(v\). If \(n\) is the number of \(d_2\)s used in a realisation \(N\) of \(v\), then \(N = (v - nd_2,n,0,\ldots,0)\) and \(|N| = v + n(1-d_2)\). Since \(d_2 > 1\), we have \(1 - d_2 < 0\). So, to minimise \(|N|\) we must maximise \(n\). To do this, let \(n = \left\lfloor \frac{v}{d_2}\right\rfloor\), where \(\left\lfloor \frac{v}{d_2}\right\rfloor\) is the floor of \(\frac{v}{d_2}\) (that is, the greatest integer less than or equal to \(\frac{v}{d_2}\)). Then \[E(v) = v + \left\lfloor\frac{v}{d_2}\right\rfloor(1 - d_2).\] The greedy realisation is also obtained by maximising the number of \(d_2\)s used. More precisely, \[G(v) = \left(v - \left\lfloor\frac{v}{d_2}\right\rfloor d_2,\left\lfloor\frac{v}{d_2}\right\rfloor,0,\ldots,0\right).\] Therefore, \(|G(v)| = E(v) = v + \left\lfloor\frac{v}{d_2}\right\rfloor\) and \(v\) is not a sneaky value. This completes the proof of the claim, and thus the solution to the question.
Let \(t > 2\) be an integer. Then I claim that for the denomination set \((1,t,t+1)\), \(2t\) is the smallest sneaky value. Let’s start by checking that \(2t\) is indeed a sneaky value. Since \(2t\) is not a denomination, and since \((0,2,0)\) is a realisation of \(2t\), we have \(E(2t) = 2\). However, \(|G(2t)| = |(t-1,0,1)| = t > 2\) and so \(|G(2t)| \neq E(2t)\). We must now show that if \(v < 2t\) it is not a sneaky value.
The claim from the solution to the previous question shows that if \(v < t + 3\), then \(v\) is not a sneaky value. Suppose now that \(t + 3 \leq v < 2t\). Then we cannot have more than one of either \(t\) or \(t+1\) in a realisation of \(v\). Therefore, there are only three possible realisations of \(v\): \(N = (v,0,0)\), \(M = (v-t,1,0)\), and the greedy realisation \(G(v) = (v-t-1,0,1)\). We have \(|N| = v\), \(|M| = v - t + 1\) and \(|G(v)| = v - t\). Therefore \(E(v) = |G(v)| = v- t\) and \(v\) is not a sneaky value.
Let \(G(v) = (n_1,n_2,\ldots,n_k)\). The intuition behind this result is that you can obtain the greedy realisation of \(v\) from that of \(v - d_k\) by simply adding one more \(d_k\). Equivalently, our intuition suggests that \(G(v-d_k) = (n_1,n_2,\ldots,n_{k-1},n_k-1)\).
To show that this is true, we will explicitly write out a formula for \(G(v) = (n_1,n_2,\ldots,n_k)\), defining each \(n_i\) recursively.
The greedy realisation is obtained by first making \(n_k\) as large as possible. To do this we set \[n_k = \left\lfloor \frac{v}{d_k}\right\rfloor,\] where \(\lfloor\alpha\rfloor\) is the floor of \(\alpha\), which is the greatest integer less than or equal to \(\alpha\). So, we have \(n_k\) copies of the denomination \(d_k\), which leaves us with \(v_{k-1} = v - n_kd_k\) remaining to make up from the other denominations. We now go to the next-largest denomination, and repeat the process.
More explicitly, let \[n_{k-1} = \left\lfloor \frac{v_{k-1}}{d_{k-1}}\right\rfloor.\] Adding \(n_{k-1}\) copies of \(d_{k-1}\) to the realisation leaves \(v_{k-2} = v_{k-1} - n_{k-1}d_{k-1}\). We can now continue in this manner. In general, for each integer \(i\) satisfying \(1 \leq i < k\) define \[v_{k-i} = v_{k-(i-1)} - n_{k-(i-1)}d_{k-(i-1)} \quad \text{ and } \quad n_{k-i} = \left\lfloor \frac{v_{k-i}}{d_{k-i}} \right\rfloor.\] Note that when \(i = k-1\) we get \(n_1 = v_1\), which is the number of \(1\)s used in the greedy realisation.
With the \(n_i\) defined this way, the greedy realisation of \(v\) is \(G(v) = (n_1,n_2,\ldots,n_k)\).
Now, let \(v > d_k\) and let \(w = v - d_k\). Let \(G(w) = (m_1,m_2,\ldots,m_k)\). We have \[m_k = \left\lfloor \frac{v - d_k}{d_k}\right\rfloor = \left\lfloor \frac{v}{d_k} - 1\right\rfloor = \left\lfloor\frac{v}{d_k}\right\rfloor - 1 = n_k - 1.\] Furthermore, \[w_{k-1} = w - m_kd_k = v - d_k - (n_k - 1)d_k = v - n_kd_k = v_{k-1}.\] Therefore, for each integer \(i\) satisfying \(k > i \geq 1\) we have \(n_{k - i} = m_{k-i}\). Putting all of this together we have that if \(G(v) = (n_1,n_2,\ldots,n_k)\), then \[G(v - d_k) = (n_1,n_2,\ldots,n_{k-1},n_k - 1).\] Therefore, \(|G(v - d_k)| + 1 = |G(v)|\).
Suppose \(N = (n_1,n_2,\ldots,n_k)\) is a realisation of \(v - d_i\) satisfying \(|N| = E(v - d_i)\). Then \(N' = (n_1,n_2,\ldots,d_{i-1},d_i + 1,d_{i+1},\ldots,d_k)\) is a realisation of \(v\). Furthermore, \[|N'| = |N| + 1 = E(v - d_i) + 1.\] By the definition of \(E(v)\), we have that \(E(v) \leq |M|\) for all realisations \(M\) of \(v\). Therefore, \(E(v) \leq E(v - d_i)+1\).
Now to address the question of when \(E(v) = E(v - d_i)+1\). Let’s assume the equality holds and see what comes of it.
Let \(M = (m_1,m_2,\ldots, m_k)\) be a realisation of \(v - d_i\) satisfying \(|M| = E(v - d_i)\). Then \(M' = (m_1,m_2,\ldots,m_{i-1},m_i + 1,m_{i+1},\ldots,m_k)\) is a realisation of \(v\) satisfying \(|M'| = E(v - d_i) + 1 = E(v)\). Therefore, if \(E(v) = E(v - d_i) + 1\), then there exists a realisation \(N = (n_1,n_2,\ldots,n_k)\) of \(v\) such that \(n_i > 0\) (that is, the denomination \(d_i\) is used) and \(|N| = E(v)\).
Let’s see if the converse holds. Assume now that \(N = (n_1,n_2,\ldots,n_k)\) is a realisation of \(v\) so that \(|N| = E(v)\) and that \(n_i > 0\). Then \(N' = (n_1,n_2,\ldots,n_{i-1},n_i-1,n_{i+1},\ldots,n_k)\) is a realisation of \(v - d_i\) satisfying \(|N'| = |N| - 1 = E(v) - 1\). However, we know from the inequality in the first part of this question that \(E(v) - 1 \geq E(v - d_i)\). We also know by the definition of \(E(v - d_i)\) that \(|N'| \geq E(v - d_i)\). Putting all of this together we have \[E(v- d_i) \geq E(v) - 1 = |N| - 1 = |N'| \geq E(v - d_i).\] The only way this can happen is if \(E(v - d_i) = E(v) - 1\).
We have proved the following statement. Suppose \(d_i < v\). Then \(E(v) = E(v - d_i) + 1\) exactly when there exists a realisation \(N = (n_1,n_2, \ldots,n_k)\) of \(v\) such that \(|N| = E(v)\) and \(n_i > 0\).
First recall the claim from the solution to Question 3(a), which says that if \(v < d_3 + 2\), then \(v\) is not a sneaky value. Combining that claim with the assumptions given in the question, we have that for all \(v < d_{k-1} + d_k\), \(v\) is not a sneaky value.
We will now proceed using a technique known as induction. Here’s the idea. To prove that some \(v \geq d_{k-1} + d_k\) is not a sneaky value, we will assume that for all values \(w < v\), \(w\) is not a sneaky value. From that assumption, we will try to prove that \(v\) is not a sneaky value.
This technique actually proves infinitely many statements at once, and here’s why it works. From what we’ve deduced so far, we know that for all \(w < d_{k-1} + d_k\), \(w\) is not a sneaky value. So, assuming we can prove what we want to, we will then be able to deduce that \(v = d_{k-1} + d_k\) is not a sneaky value. This result in turn will imply that \(v + 1\) is not a sneaky value, which then implies \(v + 2\) is not a sneaky value, and so on forever! The fact that this works is actually a fundamental defining property of the natural numbers. With that in mind, let’s do it!
Let \(v \geq d_{k-1} + d_k\) and assume that for all \(w < v\), \(|G(w)| = E(w)\) (that is, \(w\) is not a sneaky value). Now suppose that \(N = (n_1,\ldots,n_k)\) is a realisation of \(v\) satisfying \(|N| = E(v)\). Choose an \(n_i\) so that \(n_i > 0\) (which must exist since \(v >0\)).
If \(n_i = n_k\), then \[|G(v)| = |G(v - d_k)| + 1 = E(v - d_k) + 1 = E(v)\] where the first equality is by \(4\)(a), the second equality is by our assumption that \(v - d_k\) is not a sneaky value, and the third equality is from the solution to \(4\)(b). Therefore, \(v\) is not a sneaky value.
If \(n_i\neq n_k\), then \[\begin{align*} |G(v)| &= |G(v - d_k)| + 1 && \text{by 4(a)}\\ &= E(v - d_k) + 1 && \text{by our assumption} \\ &\leq E(v - d_k - d_i) + 2 && \text{by 4(b)} \\ &\leq |G(v - d_k - d_i)| + 2 &&\\ &= |G(v - d_i)| + 1 && \text{by 4(a)} \\ &=E(v - d_i) + 1 && \text{by our assumption} \\ &=E(v) && \text{by the solution to 4(b)} \\ & \leq |G(v)|.\end{align*}\] The important part of this chain of equalities and inequalities is that \[|G(v)| \leq E(v) \leq |G(v)|,\] which can only happen if \(|G(v)| = E(v)\). Therefore, \(v\) is not a sneaky value, completing the proof.
Code will not be explicitly produced here, but an algorithm will be described that we know works due to the previous questions.
Question 4(c) and the claim in the solution to Question 3(a) shows us that if a sneaky value exists, then the smallest sneaky value \(v\) satisfies \(d_3 + 1< v <d_{k-1} + d_k\).
Therefore we only have to check finitely many values of \(v\) and decide whether or not \(v\) is a sneaky value. This is possible to do on a computer since if \((n_1,n_2,\ldots,n_k)\) is a realisation of \(v\), we must have \[n_i \leq \left\lfloor \frac{v}{d_i}\right\rfloor\] for all \(i\). Therefore there are finitely many possible realisations of \(v\). The solution to 4(a) gave an explicit algorithm to compute the greedy realisation of \(v\), and so we can check each realisation \(N\) of \(v\) and determine whether or not \(|N| < |G(v)|\).
All of these checks can be done in a finite number of steps, and can therefore be programmed into a computer (although this can certainly be implemented more efficiently).
If there is a value \(v\) in the finite range \(d_3 + 1< v <d_{k-1} + d_k\) and a realisation \(N\) of \(v\) satisfying \(|N| < |G(v)|\), then the denomination set \((d_1,d_2,\ldots,d_k)\) admits a sneaky value (and one of the sneaky values is \(v\)). If for every \(v\) in the range \(d_3 + 1 < v < d_{k-1} + d_k\), all realisations \(N\) of \(v\) satisfy \(|N| \geq |G(v)|\), then the denomination set does not admit a sneaky value.
Can you come up with a more efficient algorithm than the one described here, and prove that it works?