Pay each amount with at most two coins

Question

Euro cent coins come in the denominations 1, 2, 5, 10, 20 and 50 cents.

You are inconvenienced by the fact that you need a lot of coins to pay each amount up to 100 cents. To pay 99 cents, you need 6 coins.

You want to come up with a different coinage system that allows you to pay any amount from 1-100 cents with at most two coins.

Your first idea is to use 18 coin denominations: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90

A friend comes over and tells you he found a better solution that uses only 16 different denominations.

What did he find?

Answer 1

An easy lower bound is

$14$, arising from the fact that $d$ denominations can cover at most $\binom{d+1}{2}$ distinct amounts, so we must have $\binom{d+1}{2} \ge 100$.

The minimum turns out to be

$16$, attained by $\{1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52\}$.

You can solve the problem via integer linear programming as follows. Let $C=\{1,\dots,100\}$ be the set of coins. Let $P=\{(i,j): 1 \le i \le j \le 100\}$ be the set of pairs of coins. Let binary decision variable $x_i$ indicate whether coin $i$ is selected, and let binary decision variable $y_{ij}$ indicate whether pair $(i,j)$ is used. The problem is to minimize $\sum_{i\in C} x_i$ subject to \begin{align} x_a + \sum_{(i,a-i)\in P} y_{i,a-i} &\ge 1 && \text{for all $a\in C$} \tag1\label1 \\ y_{ij} &\le x_i && \text{for all $(i,j)\in P$} \tag2\label2 \\ y_{ij} &\le x_j && \text{for all $(i,j)\in P$} \tag3\label3 \end{align} Constraint \eqref{1} forces amount $a$ to be represented with either one or two coins. Constraints \eqref{2} and \eqref{3} force coins $i$ and $j$ to be selected if pair $(i,j)$ is used.

See also https://oeis.org/A001212

Answer 2

1, 3, 4, 7, 8, 9, 16, 17, 21, 24, 35, 46, 57, 68, 79, 90

Didn't do anything clever here, just had random bruteforce code running that luckily turned up a result.