Three coins for the fair king

Question

Based on the question Eight coins for the fair king:

I saw a comment saying "There isn't a good solution known even with three coins in all cases".

So the challenge here is to try to solve the same problem placed above, except with only 3 coins.

I've tried to solve it myself and the best combination I could get to was

Coins of 1, 2 and 5, which can get me to a maximum of 12.

The highest number that follows the rules wins, and if there's proof that it's definitely the highest answer possible, it gets the tick.

Note: You may only use up to 3 coins to pay every amount, rather than 8.

Answer 1

Fact 1:

There must be a $1 coin

Fact 2:

2nd-value coin <=4, else would overflow

Proof:

Exhaustion...

Maximizing possibilities:

Notation: (x,y,z) : highest possible value

Possibility 1: (1,2,?)

(1,2,3):9
(1,2,4):10
(1,2,5):12(@S.M. in question)
(1,2,6):10
(1,2,7):11
(1,2,8+):7
For (1,2,?), (1,2,5):12=greatest

Possibility 2: (1,3,?)

(1,3,4):12
(1,3,5):11
(1,3,6):10
(1,3,7):11
(1,3,8):12
(1,3,9+):7
For (1,3,?), (1,3,8):12=greatest

Possibility 3: (1,4,?)

(1,4,5):15(Credits to @M)
(1,4,6):13
(1,4,7):9
(1,4,8+):6
For (1,4,?), (1,4,5):15=greatest

Overall:

(1,4,5):15=greatest

Answer 2

Anders Kaseorg's answer on the 8/8 list has the most optimal N/N answers up to N = 7 in a spoiler. And he has...

{1, 4, 5}

With a little enumeration, it's easy to see that you can use that set to get up to...

15.

EDIT It's actually pretty simple to reason this out without brute forcing it (too much).

Say you have three denominations of coins - A, B, and C. Then clearly one of them has to be worth #1, or else you can't pay for things that are worth #1. So let's let A be worth #1. Now, assuming that C is the most valuable form of coinage, the most you can pay is #3C.

However, what if you want to pay #3C-1? We can safely assume that you'd have to use either 2C+A or 2C+B. But if you can use A, then C would have to be worth #2, which you can rule out with some quick figuring ({1,2,3} can get you #9, which {1, 1 < n < 2, 2} can't). So you're left with B being C-1.

As a result, you only need to check triples of the form {1, N, N+1}, where N can be at most 4.

Answer 3

This is a little bit (read: a lot bit) of trickery, but

I can get up to 44 with coins of -1, 1, 10. The -1 helps because it allows you to get a units digit of 6 through 9.

I can't prove this is optimal, but it's a start (and I'm not sure if this is even good for the kingdom to have this type of coin :P)