4. A nontrivial case

For k=3 we have the following lower bound.

Proposition Let 0 <= i < (m-1)/2. Then the set W = {v,w,w+1} with v = 2m-2i-1 and w = (4i+3)m-(i+1)(4i+1)-1 achieves L(W) = (m-2i)(w+1)+i.

Proof Give the three coins weights (c,d-j,j) to get the value cv+dw+j. We shall only use nonnegative d. This payment is allowed when -h <= j <= d+h, where h is nonnegative and |c|+d+2h <= m. Let us call the interval [cv+dw-h,cv+dw+d+h] the (c,d)-interval. Let us say that an interval J may follow an interval I when the first element of J is not more than 1 larger than the last element of I. Clearly the interval (0,0) contains 0 and the interval (0,m-2i) contains (m-2i)(w+1)+i, so in order to prove that L(W) >= (m-2i)(w+1)+i it suffices to make a chain of intervals, where each may follow the previous one, starting at (0,0) and ending at (0,m-2i).

Now if c >= 0, then the (c,d)-interval may be followed by the (c-f,d+1)-interval if m+fv-w >= (|c|+|c-f|)/2, e.g. if 0 <= c <= f and m+fv-w >= f/2.

On the other hand, if c <= 0 and d >= 1, then the (c,d)-interval may be followed by the (c+f+1,d-1)-interval if m-(f+1)v+w+1 >= (|c|+|c+f+1|)/2, e.g. if -f-1 <= c <= 0 and m-(f+1)v+w+1 >= (f+1)/2.

Clearly, we want f = [w/v]. In our case v = 2m-2i-1 and w = (4i+3)m-(i+1)(4i+1)-1 we find w = (2i+1)v + m-i-1, so that f = 2i+1 and one checks that the required inequalities do hold.

So, each interval is followed by another, and c/f+d increases, so we do not loop. This stops when |c|+d > m. Now if c > 0 and the (c,d)-interval is OK (that is, c+d <= m), we can follow it by the (c-f,d+1)-interval provided d <= m-f. And if c < 0 we can follow the (c,d)-interval by the (c+f+1,d-1)-interval provided d <= m-f+1. Finally, if c = 0 we can follow the (c,d)-interval by the (c-f,d+1)-interval for d <= m-f-1, while the (0,m-f)-interval may be followed by the (f+1,m-f-1)-interval, which ends at (f+1)v+(m-f-1)(w+1) = (m-f)(w+1)+m-i-1 and can be followed again by the (1,m-f)-interval which starts at v+(m-f)w-i = (m-f)(w+1)+m-i.

This proves the lower bound. And equality holds since (m-2i)(w+1)+i+1 cannot be paid using at most m coins: if the number of coins w or w+1 is not m-2i then we are too far away from the goal to make up the difference with a few coins of value v. (Use 2w = (4i+3)v-1.) And if d=m-2i we find cv+j = m-i+1 for some j with -h <= j <= m-2i+h and |c|+2h <= 2i. Now c=0, but we are just outside the (0,m-2i)-interval. Contradiction. Hence L(W) = (m-2i)(w+1)+i.

Picture for m=6, i=1, v=9, w=31, L=129. Look at (c,d-j,j), which yields 9c+31d+j, for all admissible j. Vertically c, horizontally d.

Picture for m=10, i=2, v=15, w=82, L=500.

We still have a free parameter i to choose. Putting x = i/m we see roughly (for m tending to infinity) L = 4x(1-x)(1-2x)m^3, and have to optimize this for 0 < x < 1/2. The optimum is x = 1/2 - sqrt(3)/6 = 0.211, slightly less than 2/9. For 6 <= m <= 27 the choice i = [2(m-1)/9] is optimal, and actually gives the value of L(3,m), as follows from exhaustive search, cf. the table below. For m = 28 the best choice is i = 5, while [2(m-1)/9] = 6. (And again the resulting system is best possible.)

The polytope has (2m+1)(2m^2+2m+3)/3 points, so the theoretical maximum would be half of that, about (2/3)m^3. We find about 0.385*m^3, about 57% of that.