Eight coins for the fair king

Question

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?

3. 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?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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.