Doge, the king? (Faints)

1,4,6,14,15 you can easily made any number from 1 to 36 by adding at maximum 3 coins of above mentioned value.

1,3,9,27 - minimum denominations

powers of 3

Ans = 40

Definition: Let $c,\:d$ be the number of coins and denominations, and $v(\{c\})$ the number of different values using exactly $c$ coins.

Recall some combinatorics:

Theorem: If we choose $k$ unordered elements from a set of $n$ distinct elements with repetitions, there are $\binom{k+n-1}{n-1}$ possible choices.

First we show there can be no solution with $d < 5$ denominations. Notice that we may choose any coin more than once, so the above theorem will be useful! Notice as well that different combinations of coins may lead to the same value, so we can only give an upper bound: The maximum number of different values (when they are pairwise disjoint) is given by $\begin{aligned} v(\{c\})&\leq\binom{c+d-1}{d-1},&&&& v(\{1\leq c\leq c_{max}\})&\leq\sum_{c=1}^{c_{max}}\binom{c+d-1}{d-1}=\sum_{c=0}^{c_{max}}\binom{c+d-1}{d-1}-1=\binom{c_{max}+d}{d}-1 \end{aligned}$

Plug in $c_{max}=3$ to get $v(\{1\leq c\leq 3\})\leq\frac{(d+3)(d+2)(d+1)}{6}-1\leq 34<36\quad\text{for any}\quad 1\leq q\leq 4$

One can obtain (at most) 34 distinct values with four or less coins. Any minimal solution must have (at least) $d=5$ denominations!

Check all denominations with $d=5$ using maxima - even with the elimination scheme used in the program below there are several hundred cases left. The only solution returned is

$(1;\:4;\:6;\:14;\:15)\quad\Rightarrow\quad 1+4+6+14+15=\boxed{40}$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/* 
    in each iteration, adds one monomial to p such that the next polynomial
    has greater degree and p^3 has less vanishing coefficients of order <= N

    inputs:
        iter: iteration depth = number of coins left to choose
        p: current polynomial in x, should have coefficients in {0; 1}
        N: max degree p may have
        degree: current degree of p

    outputs:
        all polynomials p such that p^3 has no vanishing coefficients of order <= N
*/

iteration(iter, N, p, degree) := block([i, coeff, d, q],
    q : expand(p**3),
    coeff : makelist(coeff(q, x, k), k, 0, N),
    if not member(0, coeff) then (display(p), return(0)),
    if(iter <= 0) then return(0),

    /* find first non-zero coefficient in q=p^3 */
    d : 0,
    for c in coeff do
        if(c = 0) then return(0) else d : d + 1,

    if (d > N) then return(0),
    for i : degree+1 thru d do iteration(iter-1, N, p+x**i, i)
)$

iteration(5, 36, 1, 0)$

• I think the answer must be modified. we can make numbers from 1 to 36 using 1,2,4,10,17
• 1=1
• 2=2
• 3=1+2
• 4=4
• 5=4+1
• 6=4+2
• 7=4+3
• 8=4+4
• 9=4+4+1
• 10=10
• 11=10+1
• 12=10+2
• 13=10+2+1
• 14=10+4
• 15=10+4+1
• 16=10+4+2
• 17=17
• 18=17+1
• 19=17+2
• 20=17+2+1
• 21=17+4
• 22=17+4+1
• 23=17+4+2
• 24=10+10+4
• 25=10+17-2
• 26=10+17-1
• 27=10+17
• 28=10+17+1
• 29=10+17+2
• 30=10+10+10
• 31=17+10+4
• 32=17+17-2
• 33=17+17-1
• 34=17+17
• 35=17+17+1
• 36=17+17+2
• So the answer must be 34