Gfrktyl

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.

The rules are:

1. You must create 3 coins of different value, no more.




2. Any sum of money must be paid with only 3 coins. This sum should be paid without giving change.




3. You must set N such that no price is allowed to be greater than N.

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 N = 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.

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

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.

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)