The Royal Mint of Alphagonia

Question

In the Kingdom of Alphagonia nothing can be bought for less than 30 alphas, the local currency.

1) What three denominations of coins should the kingdom mint so that as many as possible of the (integer) amounts between 30 and 100 alphas (both inclusive) can be paid using no more than three coins?

2) What is the least k such that Alphagonia can mint just three different denominations of coins with which any amount between 30 and 100 alphas can be paid using at most k coins?

Answer 1

Partial Answer (Part 1):

I think the answer is:

$30,31,34$

It is possible to make,

$18$ amounts out of $19$ possible with these three coins.

Proof:

First we count the maximum possible number of sums we can make with three coins.
Case 1 ($3$ coins chosen, all $3$ are different): We have just $1$ possible sums here.
Case 2 ($3$ coins chosen, exactly $2$ coins are equal): We have $6$ possible sums here ($3$ possible choices for the equal coins, multiplied by $2$ possible choices for the other coin).
Case 3 ($3$ coins chosen, all $3$ coins are same): We have $3$ possible sums here, one for each coin choice.
Case 4 ($2$ coins chosen, the $2$ coins are same): We have $3$ possible sums here, one for each coin choice.
Case 5 ($2$ coins chosen, the $2$ coins are different): We have $3$ possible sums here, choices for the coin we leave out.
Case 6 ($1$ coin chosen): We have $3$ possible sums here, one for each coin choice.
So there are $1+6+3+3+3+3=19$ sums possible. We can show that we cannot stuff all $22$ into the range $[30,100]$ and that $30,31,34$ produces $12$ which is enough to imply that it is one of the maximum. Assume for the sake of contradiction that $13$ is possible. Then $3\cdot\text{(largest coin)}$ must be less than or equal to $100$ which implies that the largest coin is less than or equal to $33$. Also when we take just the smallest coin it must be greater than equal to $30$. So the three coins are in the range $[30,33]$.
We verify that it is not possible to get $19$ in this case: (assume that the coins are different; if two of them were equal we obviously can't get $19$)
$30,31,32\rightarrow 30+32=31+31$
$30,31,33\rightarrow 30+30+33=31+31+31$
$31,32,33\rightarrow 31+33=32+32$
As each possible case gives overlaps between sums we can't get $19$.
Now we show that $30,31,34$ gives $18$. Note that $34+34+34=102$ is not possible. Also it's obvious to see that there are no overlaps with two coins: we have to check only for $3$ coins. Let the coin values be $a,b,c,d,e,f$ such that $a+b+c=d+e+f$, and assume that $\text{ max(a,b,c)<max(d,e,f)}$ (if $\text{ max(a,b,c)>max(d,e,f)}$ swap $(a,b,c)$ and $(d,e,f)$, and if $\text{ max(a,b,c)=max(d,e,f)}$ then removing the maximum coin from both sets reduces it to the $2$ coin case which we already ruled out)
Case 1: ($\text{ max(a,b,c)=31, max(d,e,f)=34 }$):
Here $\text{max(a+b+c)=93}$, obtained when $a=b=c=31$, and $\text{ min(d+e+f)=94}$ when $d=e=30,f=34$ so $a+b+c=d+e+f$ is not possible.
Case 2: ($\text{ max(a,b,c)=30, max(d,e,f)=34 }$): Identical to the above case.
Case 3: ($\text{ max(a,b,c)=30, max(d,e,f)=31 }$):
Here $\text{max(a+b+c)=90}$, obtained when $a=b=c=30$, and $\text{ min(d+e+f)=91}$ when $d=e=30,f=31$ so $a+b+c=d+e+f$ is not possible.
So we ruled out all overlaps, so the only sum which gets "wasted" is $102$, and thus this gives $18$ possible amounts which is the maximum possible.

Part 2:
We could get:

$k=8$

with the coin set:

$1,13,18$

Method:

We mark the numbers that can be expressed as a sum of multiples of $13$ and $18$, and after that we just have to take the closest marked number less than it for all integers, and add the difference to the number of $13$'s and $18$'s in the number. \begin{array}{|c|c|}\hline\text{ Number }&31 & 36 & 39 & 44 & 49 & 52 & 54 & 57 & 62 \\ \hline\text{ Add } &2& 2& 3& 3& 3& 4& 3& 4& 4\\ \hline\end{array} \begin{array}{|c|c|}\hline\text{Number}&67&70&72&75&78&80&83&85&88&90&93&96& 98 \\ \hline\text{ Add }&4&5&4&5&6&5&6&5&6&5&6&7&6\\\hline\end{array}

As @JaapScherphuis confirmed using a program in his answer this is the minimum possible.

Answer 2

Suppose we can use up to $k$ coins of three denominations (like in the second question). If you imagine also having a fourth denomination of $0$, then you can always use exactly $k$ coins to make the values. This viewpoint allows us to calculate the number of possible combinations of $k$ coins using the stars and bars method, which gives $\binom{k+3}{3}$. For $k=3$ this is $\binom{6}{3}=20$. Of course the combination consisting only of the $0$-value coins should be discounted, so there are $19$ ways to choose up to three coins.

I used a computer to check all the possibilities. It turns out there are $64$ possible choices of three denominations which allow $18$ distinct values from $30$ to $100$ to be made using three coins. There is no choice that can make $19$ different values that all fall in that range.

                                                      15,31,33  15,32,33
                                            16,30,33  16,31,33
    17,30,31  17,31,32                      17,30,33  17,31,33
    18,30,31  18,31,32  18,30,32                      18,31,33  18,32,33
    19,30,31  19,31,32  19,30,32            19,30,33  19,31,33  19,32,33
              20,31,32                                20,31,33  20,32,33
    21,30,31            21,30,32                      21,31,33  21,32,33
    22,30,31            22,30,32  22,31,32
    23,30,31            23,30,32  23,31,32  23,30,33  23,31,33  23,32,33
    24,30,31            24,30,32  24,31,32            24,31,33  24,32,33
    25,30,31            25,30,32  25,31,32  25,30,33  25,31,33  25,32,33
    26,30,31                      26,31,32  26,30,33  26,31,33  26,32,33
    27,30,31            27,30,32  27,31,32                      27,32,33
                                  28,31,32  28,30,33  28,31,33  28,32,33
                                            29,30,33            29,32,33
                                                      30,31,33  30,32,33  30,31,34

Now the second question.
Since $k=5$ coins can make at most $56$ distinct values (or $55$ if we discount the value of $0$), we need at least $6$ coins. Again I used a computer for this, and it turns out that

$k=8$ is the minimum. Using just $7$ or fewer coins it is not possible to cover the whole range from $30$ to $100$. I don't see an obvious way to show this.

There are $42$ possible demonination triplets that work. There is one triplet, $(5,14,16)$, that can even make all values from $28$ to $118$ with up to $8$ coins. The triplet $(2,11,16)$ can make all values from $10$ to $100$.

With up to $7$ coins the best is $(4,14,15)$, which only covers range $30$ to $94$.
With up to $6$ coins the best ones are $(5,11,12)$, $(7,11,12)$, and $(6,11,13)$ which cover the range $30$ to $72$.

Answer 3

Since the question allows money back from the seller by OP, the answer for 3 denominations will be

$4,28,33$ or $4,29,34$, which is found by a code.

with

total $55$ amount of alphas.

For example;

to buy an item valued as $30$, you need to give 33+33 coins and get a change back 3 coins with value of 28+4+4 coins. But without changes, it is not possible to buy an item with 30.

For second part

the answer becomes much faster with

k=4, such as 1,14,33. actually there are many possible answers, but 4 of them would be enough for every single alpha with paying and getting change back.

I am not sure how it can be shown without brute force.