I need to check whether a given coin system of five coins, $\$ = <1,c_2,c_3,c_4,c_5>$, is canonical, that is, a system in which the greedy algorithm provides the way to make change using the fewest number of coins.
For example, the US paper currency system $\$_{US}=<1,5,10,20,50>$ is canonical, but the system $\$_{NC}=<1,3,4,20,50>$ is non-canonical, as, among other values, $6=4+1+1$ would be the greedy representation, but $6=3+3$ is the optimal representation, as it uses one fewer coin.
A helpful reference I found is Xuan Cai: Canonical Coin Systems for Change-Making Problems, in which neccesary and sufficient conditions are given for, among others, the case for coin systems with five coins. However, I am getting conflicting results when following these conditions in the paper, likely owing to my own misunderstanding. Here is the relevant theorem:
Theorem 9: A coin system $\$=<1,c_2,c_3,c_4,c_5>$ is non-canonical if and only if $\$$ satisfies exactly one of the following conditions:
1) $\$=<1,c_2,c_3>$ is non-canonical.
2) $\$ \ne <1,2,c_3,c_3+1,2c_3>$.
3) $\lvert GRD_{\$}((k+1) \cdot c_4)\rvert > k+1$ with $k \cdot c_4<c_5<(k+1) \cdot c_4$.
The way to check if a coin system with three coins is non-canonical is provided by Theorem 4:
Theorem 4: The coin system $=<1,c_2,c_3>$ is non-canonical if and only if $0<r<c_2-q$ where $c_3=qc_2+r$ and $r \in [0, c_2-1]$.
Here are two examples of coin systems checked with Theorem 9.
1) $\$_1=<1,5,10,20,50>$.
First we check $<1,5,10>$ by Theorem 4. We see that $10=2 \cdot 5 + 0$, giving $r = 0$, and $q = 2$. Thus $0 \nless r$, so $<1,5,10>$ is canonical, and so $\$_1$ does not meet the first condition.
Next, we check that $\$_1 \ne <1,2,c_3,c_3+1,2c_3> = <1,2,10,11,20>$, which is true. Thus, $\$_1$ does meet the second condition.
Finally, we check the third condition. We find $k=2$ satisfies $2 \cdot 20 < 50 < 3 \cdot 20$, and so we find $GRD_{\$_1}(3 \cdot 20 = 60) = 50+10$. Thus, $\lvert GRD_{\$_1}(60)\rvert = 2$, as two coins are used. Thus $2 \ngtr 3$, and so $\$_1$ does not meet the third condition.
In conclusion, $\$_1$ meets exactly one of the three conditions, condition 2), and so, by Theorem 9, $\$_1$ is non-canonical. However, we know this is not true, as $\$_1 = \$_{US}$ from above, a system known to be canonical.
2) $\$_2=<1,3,4,20,50>$.
First we check $<1,3,4>$ by Theorem 4. We see that $4=1 \cdot 3 + 1$, giving $r = 1$, and $q = 1$. Thus $0 < r < 2$, so $<1,3,4>$ is non-canonical, and so $\$_2$ does meet the first condition.
Next, we check that $\$_2 \ne <1,2,c_3,c_3+1,2c_3> = <1,2,4,5,8>$, which is true. Thus, $\$_2$ does meet the second condition.
Finally, we check the third condition. We find $k=2$ satisfies $2 \cdot 20 < 50 < 3 \cdot 20$, and so we find $GRD_{\$_1}(3 \cdot 20 = 60) = 50+4+4+1+1$. Thus, $\lvert GRD_{\$_1}(60)\rvert = 5$, as five coins are used. Thus $5 > 3$, and so $\$_2$ does meet the third condition.
In conclusion, $\$_2$ meets not exactly one but all three conditions, and so, by Theorem 9, $\$_2$ is canonical. However, we know this is not true, as $\$_2 = \$_{NC}$ from above, a system known to be non-canonical.
Either I am misinterpreting Theorem 9, or a (likely) small correction should be made in the paper. Can anyone see either where I am wrong, or how Theorem 9 should be fixed?
My hunch is that the second condition should read $\$ = <1,2,c_3,c_3+1,2c_3>$, and the wording of Theorem 9 should be "...is non-canonical if and only if $\$$ satisfies at least one of the following conditions". That way, our two examples would be consistent with their known canonicality.