9
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ we assume there is no change back from the seller with selected currency? $\endgroup$ – Oray Sep 10 at 11:39
  • $\begingroup$ @Oray As I originally devised the question, no. But why not? $\endgroup$ – Bernardo Recamán Santos Sep 10 at 11:52
  • $\begingroup$ then you may want to limit the number of change back then, since if we consider 1, with unlimited change back would crack the question. $\endgroup$ – Oray Sep 10 at 11:56
  • 1
    $\begingroup$ @Zoir No, just a suggestion for an extension. The original question remains, and your work on it is appreciated. $\endgroup$ – Bernardo Recamán Santos Sep 10 at 13:27
  • 1
    $\begingroup$ OK, thank you for the clarification!! $\endgroup$ – Zoir Sep 10 at 13:27
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to PSE! Well done, I'm sure it's correct for the first question! :D $\endgroup$ – athin Sep 10 at 4:52
  • $\begingroup$ Thank you! I've been lurking here for a couple of weeks and wanted to try it myself. $\endgroup$ – Zoir Sep 10 at 5:16
  • 1
    $\begingroup$ it seems there are more than one answer, such as 30,16,33 is another answer. $\endgroup$ – Oray Sep 10 at 5:48
  • $\begingroup$ @Oray I think 4911,4912,4914 (subtract 4881) would work too: I couldn't find any conflicts except the one I showed in the proof. $\endgroup$ – Zoir Sep 10 at 5:59
  • $\begingroup$ There are multiple combinations of 3 denominations that give k=8, but none that give k<8. {1,11,14} seems to be smallest. $\endgroup$ – Ben Aveling Sep 11 at 1:27
6
$\begingroup$

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$.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.