Problem of the Month
Problem 7: Sneaky Values

The denominations that make up the currency in Canada, ignoring those less than a dollar, are \(\$1\), \(\$2\), \(\$5\), \(\$10\), \(\$20\), \(\$50\), and \(\$100\). Using these denominations, we can realise any integer dollar value. For example, to make \(\$45\), we could use four \(\$10\)s and one \(\$5\), or two \(\$20\)s and one \(\$5\), or even forty-five \(\$1\)s. The way to realise \(\$45\) that uses the fewest items (coins or notes) is with two \(\$20\)s and one \(\$5\), which uses three items.

1. Describe, with justification, how to obtain \(\$107\) in Canada using the least number of items.

2. In the utopian (and sadly, fictitious) country of Cemcalia, the currency has notes with denominations \(1\), \(5\), \(10\), \(18\), and \(30\). Describe, with justification, how to obtain \(37\) using the least number of notes.

In order to investigate general currency systems, we will first set some notation. A denomination set is a tuple \((d_1,d_2,\ldots,d_k)\) of positive integers satisfying \(d_1 = 1\) and \(d_i < d_{i+1}\) for all \(i\). Given such a denomination set, a realisation of a value \(v\) (which must be a positive integer) is a \(k\)-tuple of non-negative integers \(N = (n_1,n_2,\ldots,n_k)\) so that \(n_1d_1 + n_2d_2 + \cdots + n_kd_k = v\). Denote the number of items used in the realisation \(N\) by \(|N| = n_1 + n_2 + \cdots + n_k\). The greedy realisation of \(v\) (denoted \(G(v)\)) is obtained by taking the largest denominations possible until the value is reached.

For example, in Canada, the denomination set is the \(7\)-tuple \((1,2,5,10,20,50,100)\). The greedy realisation of the value \(45\) is \(G(45) = (0,0,1,0,2,0,0)\) and \(|G(45)| =1 + 2 = 3\). The value \(45\) is also realised by the \(7\)-tuples \((0,0,1,4,0,0,0)\) and \((45,0,0,0,0,0,0)\) (among others).

It is not necessarily the case that the greedy realisation uses the fewest items! For a value \(v\), define \(E(v)\) to be the smallest possible number \(|N|\) over all realisations \(N\) of \(v\). For example, consider the denomination set \((1,15, 20)\). Then \(E(30) = 2\) and \(|G(30)| = |(10,0,1)| = 11\). It is a consequence of the definition of \(E(v)\) that \(E(v) \leq |G(v)|\) for all values \(v\). A value \(v\) for which \(E(v) < |G(v)|\) is called a sneaky value.

3. Find infinitely many denomination sets \((1,d_2,d_3)\) with the property that

   1. \(d_3 + 2\) is the smallest sneaky value.

   2. \(d_2 + d_3 - 1\) is the smallest sneaky value.

4. Let \((d_1,d_2,d_3,\ldots,d_k)\) be a denomination set.

   1. Show that for any value \(v > d_k\), \(|G(v - d_k)| + 1 = |G(v)|\).

   2. For all values \(v\) and all denominations \(d_i < v\), show that \(E(v - d_i) + 1 \geq E(v)\). When is the inequality an equality?

   3. Suppose there are no sneaky values \(v\) satisfying \(d_3 + 1 < v < d_{k-1} + d_k\). Prove that there are no sneaky values at all!

5. Using your favourite programming language, write a program that decides whether or not a denomination set \((d_1,d_2,\ldots,d_k)\) admits a sneaky value.