Pay each amount with at most two coins

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?

• common sense says when working with coins you only need 1 coin to PAY 99 cents since the seller will give give you one back for your hundred., (or owe you one for next time) and thats the reason the optimum number is 1+2+2+5 at each level
– K J
Aug 20, 2023 at 11:12
• Your problem is ill defined. For example in his answer Manish Kundu found 16 denominations, but to buy something costing 2 cents he'd need two 1 cent coins. Would the problem be better stated as "having sixteen coins that will pay any amount between 1 and 99 cents with just two of the coins"?
– MaxW
Aug 21, 2023 at 2:43
• @MaxW It is at most two coins. Also, you must cover 1 through 100, inclusive. Aug 21, 2023 at 3:19
• So the problem statement would be better as "having sixteen coins that will pay any amount between 1 and 100 cents with at most two of the coins." So a set of sixteen coins beginning {1,3, ...} wouldn't work because you'd need two 1 cent coins to make 2 cents.
– MaxW
Aug 21, 2023 at 6:03
• @MaxW No, the problem is to find a set of denominations, and you can use up to two coins (possibly of the same denomination) to pay each amount. Aug 21, 2023 at 12:37

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.

• I believe you can subtract six from your second last value to obtain an alternative solution.
– Neil
Aug 20, 2023 at 7:44

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.

• Was "bruteforce code" a computer solution? Aug 19, 2023 at 19:15
• @WeatherVane Looks like it, but there wasn't any no-computers tag. Aug 19, 2023 at 21:51
• Interesting. I was not able to brute-force it. I checked every possible subset of {1…100} of length 16 and it took way too long. How did you do it? Aug 19, 2023 at 23:42
• The first 10 elements have the property that they are all different modulo the difference between the 10th and subsequent elements, plus they cover all of the values up to twice the 10th element except the 11th and 12th elements and their sums with the existing elements, at which point the subsequent differences repeat, covering all the values up to 100 as desired.
– Neil
Aug 20, 2023 at 0:23