Background
I've been thinking about payments which you can do using at most two coins. This includes three possible cases:
- You pay by giving one coin of the value you owe (for example, if you have pay 10 cents, you give one 10 cent coin).
- You pay by giving two coins adding up to the value you owe (for example, if you have to pay 11 cents, you give one 10 cent coin and one 1 cent coin).
- You pay by giving one coin of a value higher than the value you owe, and get back one coin whose value is exactly the difference (for example, if you owe 9 cents, then you give one 10 cent coin and get back one 1 cent coin).
Now if you look e.g. at the Euro cent coins (values 1, 2, 5, 10, 20, 50) you can figure out that you can pay all values up to 12 cents that way, but there's no way to pay 13 cents with only two coins. So the smallest amount you cannot pay using only two coins here is 13 cents.
To save typing, in the following I'll abbreviate "payable using at most two coins" as "2-payable".
This got me thinking about giving a total number of coin types, what values should they have to maximize the smallest non-2-payable amount.
What I already know
For only one coin, the solution is obvious: The single coin has to be the value 1, because otherwise there's no way to pay a price of 1. Obviously then the minimal non-2-payable amount is 3.
For two coins, I initially though the solution would be obvious: Since the first non-2-payable amount is 3. An additional coin of value $v$ makes the values $v-1$, $v$ and $v+1$ 2-payable, therefore we want $v=4$, which makes the least non-2-payable amount $6$.
However I then discovered that this solution is indeed not optimal: I didn't consider the option not to include a coin of value $1$. It turns out the optimal set is $\{2,3\}$; this gives a least non-payable amount of $7$.
One can easily verify that this is optimal, since any allowed combination ($\{2,3,2+2,3+2,3-2,3+3\}$) gives a different value. Indeed, this allows to find an upper bound to the least non-2-payable value with $n$ coins: There are $n$ ways to pay with 1 coin, $n(n+1)/2$ ways to pay giving 2 coins and $n(n-1)/2$ ways to pay with change, which gives together are $n^2+n$ possibilities, so the least non-2-payable amount is at most $n^2+n+1$. For $n=2$, this gives an upper bound of $7$, which indeed is satisfied by the coin choice of $\{2,3\}$.
Now for three coins, that upper bound is $13$. However, using brute force (and Mathematica) I find that there are three optimal solutions for three coins, namely $\{1,5,8\}$, $\{2,4,5\}$ and $\{3,4,5\}$, with a least non-2-payable amount of $11$.
Also with brute force, I get the optimal four-coin solutions $\{1, 2, 8, 13\}$, $\{3, 6, 7, 8\}$ and $\{4, 6, 7, 9\}$ with least non-2-payable amount of $17$.
For five coins, I again get only one solution, $\{4, 8, 10, 11, 13\}$ with least non-2-payable amount of $25$.
For six coins, I aborted the brute force search code because it took too long for my patience.
I cannot see any obvious pattern in the results. I've also looked up the sequence of least non-2-payable amounts I found in OEIS but for the three results (A029715, A194069, A088803), I don't see if/how they might be related. I've also searched for the sequence of one less (the highest amount in the range of 2-payable aounts starting at 1), and got one result, A030511, which I again can tell if/how it might be related.
Mathematical formulation/Question
Given the function $$L: P(\mathbb N) \to \mathbb N, L(V) = \min\{k\in \mathbb N: \lnot\exists a,b\in V, k=a\lor k=a+b\lor k=a-b\}$$ and given an $n\in N$, how do you systematically find $n$-element sets $V$ which maximize $L$? Or at least, find the maximal $L(V)$ you can obtain with $n$-element sets?