47
$\begingroup$

You are responsible for creating new types of coins for the court.

  1. King respects the forgetful: he wants you to create 8 coins of different value, no more.

  2. King respects the feeble: he wants that any (integer) sum of money (price) could be paid with no more than 8 coins, since they can be heavy. This sum should be paid without giving change.

- But my king, no matter how big is the largest coin, you can't pay more than 8 of them! How would you pay any sum?

  1. The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N. Thus, the contradiction with the rule (2) can be satisfied.

However, you, as a wealthy customer, are very troubled with this last rule. You want to maximize N so you can continue buying ludicrously overpriced things.

What is the maximum N you can reach by creating the coin standard?

$\endgroup$
  • 6
    $\begingroup$ Related: codegolf.stackexchange.com/q/178015 $\endgroup$ – Joel Reyes Noche Dec 25 '18 at 14:08
  • 3
    $\begingroup$ "The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N." FYI, price controls tend to create shortages. This is bound to wreck the king's economy in some way, ultimately hurting the poor. ;) $\endgroup$ – jpmc26 Dec 27 '18 at 0:35
  • 9
    $\begingroup$ The answer is in this paper. $\endgroup$ – alephalpha Dec 27 '18 at 13:35
  • 1
    $\begingroup$ @ThomasBlue self-answer it and/or mark as accepted any answer giving the optimal solution. $\endgroup$ – Cœur Dec 27 '18 at 17:43
  • 1
    $\begingroup$ @ThomasBlue I made a community wiki answer giving the optimal solution, which you can accept. $\endgroup$ – isaacg Dec 28 '18 at 6:50
9
$\begingroup$

The optimal solution is

1, 8, 13, 58, 169, 295, 831, 1036

This set of coins allows N =

3485

This set of coins is given in this paper: Some Extremal Postage Stamp Bases, by Michael F. Challis and John P. Robinson.

This paper was found by @alephalpha.

$\endgroup$
27
$\begingroup$

You can do better than the greedy algorithm. With coins of value

{1, 6, 20, 75, 175, 474, 756, 785}

you can get N =

3356.

I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:

one coin: {1}, N = 1
two coins: {1, 2} or {1, 3}, N = 4
three coins: {1, 4, 5}, N = 15
four coins: {1, 3, 11, 18}, N = 44
five coins: {1, 4, 9, 31, 51}, N = 126
six coins: {1, 7, 11, 48, 83, 115}, N = 388
seven coins: {1, 7, 18, 62, 104, 244, 259} or {1, 8, 13, 66, 115, 254, 415}, N = 1137

$\endgroup$
  • 8
    $\begingroup$ Nice! I have a program which I hope is able to finish the entire search space in reasonable time (6-8 weeks). $\endgroup$ – Glorfindel Dec 25 '18 at 12:24
  • $\begingroup$ Can confirm results for up to six coins(lang is too slow for seven ones :) ). $\endgroup$ – Pavel Mikhailyuk Dec 26 '18 at 19:21
  • 1
    $\begingroup$ I'll ask my bank to print notes of 1, 5, 20, 75. Should be close enough for a happy kingdom. [edit: oh, after a search, Austria and Germany had notes of 75 in the past] $\endgroup$ – Cœur Dec 27 '18 at 2:42
  • 1
    $\begingroup$ @GauravGandhi 20+6+6+6+6+6+6+1 - good example showing that the greedy algorithm wouldn't give a good result (as starting with 20+20 would mean you won't get there) $\endgroup$ – SztupY Dec 27 '18 at 15:01
  • 4
    $\begingroup$ N = 3485 with {1, 8, 13, 58, 169, 295, 831, 1036} was found in 2002 according to cs.uwaterloo.ca/journals/JIS/VOL13/Challis/challis6.html. (article found by alephalpha) $\endgroup$ – Cœur Dec 27 '18 at 17:22
21
$\begingroup$

I can do a little better, using coins of

1, 2, 5, 13, 34, 89, 233, 610
These are the Fibonacci numbers with odd index, also found in OEIS A001519.

I can pay amounts up to (and including)

$N=1596$

(without change).

Explanation:

According to Zeckendorf's theorem, every number has a (unique) representation as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. $N=1596$ is the smallest number requiring 8 digits in the Zeckendorf representation; it's 101010101010101, corresponding to 987 + 377 + 144 + 55 + 21 + 8 + 3 + 1.
As long as the 1s are on 'even' places (counted from the right), we can use the coins to pay them. In the case of 1596, all the 1s are on 'odd' places. Generally, a number may be a mixture of odds and evens.
The trick is now to combine basic properties of Fibonacci numbers to get rid of 1s on odd places. For instance, each instance of '1010x' can be replaced by '0200(x+1)', and each instance of '1001' by '0200'. The latter is fine since it does not increase the 'coin count'; the former increases the coin count by 1.
I'm having a hard time right now to formalize the proof; I will try again later today or tomorrow. Maybe Zeckendorf isn't the way to go after all ...

One can ask what $N$ is as function of the # of different coin values and maximum # of coins in a single payment.

In this case, $N(8) = 1596$; this sequence is given by OEIS A027941. In particular, note the last comment:
number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015

$\endgroup$
  • $\begingroup$ I can confirm that this works up to 1596. 1597 requires 9 coins (610,610,233,89,34,13,5,2,1) $\endgroup$ – Dr Xorile Dec 24 '18 at 15:08
  • $\begingroup$ While this approach works for 1 or 2 coins, it fails at 3 coins: A027941 gives a value of 12, but the set {1, 4, 5} shows we can go up to 15. $\endgroup$ – Cœur Dec 27 '18 at 2:34
  • $\begingroup$ Yeah, it's something else after all. I guess I wasn't sober when I posted that :) $\endgroup$ – Glorfindel Dec 27 '18 at 8:18
  • $\begingroup$ According to the article "Remarks on the postage stamp problem with applications to computers" by R. Alter, J. Barnett, published in 1977, the Fibonacci sequence A027941 is proved to be a lower bound to this problem. So your answer is definitely valuable for a quick estimate for larger number of coins. $\endgroup$ – Cœur Dec 27 '18 at 17:40
16
$\begingroup$

I can improve a little bit further using the coins

1, 5, 16, 51, 130, 332, 471, 1082.
chosen by a greedy computer program

With those coins I can express (with at most 8 coins, and no change) every non negative integer up to (and including)

2721

I'm not sure this is the definitive answer, as I was able to outperform the greedy algorithm for a smaller number of coins.

Explanation of how the program works:

There must be a 1 value coin, or else it will impossible to pay 1. The program calculates what is the smallest unobtainable value with the current combination of coin values. Then it tests every integer greater than every coin so far, but smaller (or equal) to the unobtainable value. It picks the one that increases this limit the furthest.

$\endgroup$
6
$\begingroup$

I would say:

255

Since:

Coins values are 1 2 4 8 16 32 64 128
By which you can pay any value, from 1 to 255

Second try:

If we allow duplicate coins, we can pay:
N = 382
Because we can pay any of the below:
2 * 128
2 * 128 + 1 + 2 + 4 + 8 + 16 + 32
2 * 128 + 64
2 * 128 + 64 + 1
2 * 128 + 64 + 1 + 2 + 4 + 8
2 * 128 + 64 + 16
2 * 128 + 64 + 16 + 1 + 2 + 4 + 8
2 * 128 + 64 + 32
2 * 128 + 64 + 32 + 1 + 2 + 4 + 8
...
2 * 128 + 64 + 32 + 16 + 8 + 4 = 380
2 * 128 + 64 + 32 + 16 + 8 + 4 + 1 = 381
2 * 128 + 64 + 32 + 16 + 8 + 4 + 2 = 382

$\endgroup$
  • $\begingroup$ ROT13(Gur pbvaf V guvax ner pbeerpg, ohg A vf abg. Nf sbe rknzcyr, jvgu 2k 128 pbvaf lbh jbhyq unir n inyhr bs 256) $\endgroup$ – Jamie Barker Dec 24 '18 at 11:30
  • $\begingroup$ Jryy, jr pna fnl 8 k 128 = 1024, ohg va guvf pnfr, jr pna'g unir 1023 ol 8 pbvaf $\endgroup$ – Ahmed Ashour Dec 24 '18 at 11:32
  • $\begingroup$ V ernyvfr gung, ohg lbh fgvyy unir n uvture znkvzhz guna 255 :Q $\endgroup$ – Jamie Barker Dec 24 '18 at 11:35
  • 13
    $\begingroup$ - Wait! - says the blacksmith. - I just can't accept this wild waste of material. Why would anyone need a coin valued 2, 4 or 8 if I can just pay them in single drahms? I can't deny your wiseness - I see, they become necessary later, yet still, I believe you can find a better solution. $\endgroup$ – Thomas Blue Dec 24 '18 at 12:01
2
$\begingroup$

This could be absolutely ridiculous since I didn't use anything to prove it is correct for all numbers but here goes:

If you can repeat coins (implied by "no matter how big is the largest coin, you can't pay more than 8 of them"), that means that with a coin of 1 we can get up to 8, then we introduce the 9, the maximum amount we can get with coins of 9 is 72, then we introduce the 73 and so on, leading us to the coins

1, 9, 73, 585, 4681, 37449, 299593 and 2396745

which would lead to a maximum amount of 19173952, using 8 2396745 coins.

TLDR, the answer to the question would be (according to the above):

19 173 952

Edit:

Well, it is incorrect, I could've simply tested it by trying to get 71; you'd need 7 coins of 9 and you'd only be left with 1 of 1, which would give us 64.

I suppose I'll leave this up anyways as an example of bad reasoning.

Also doubt it is correctly solvable to its full extent without using computers / a specific algorithm.

$\endgroup$
  • $\begingroup$ As much as this answer is wrong, the last sentence is the point. The standard coin problem gets into some complicated number theory because the costs you can't make shrink as you add more coins, so the divisibility relations get very ugly (it's the wrong way somehow). There isn't a good solution known even with three coins in all cases, thought you can work it out with algorithms and bounds. $\endgroup$ – theREALyumdub Dec 26 '18 at 20:04

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.