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.

0 | 1 | 2 | 3 | 4 | |||

-3 | 3- 6 | 35-37 | 66-69 | ||||

-2 | 12-15 | 43-47 | 75-78 | 106-110 | |||

-1 | 20-25 | 52-56 | 83-88 | 115-119 | |||

0 | 0- 3 | 29-34 | 60-66 | 92-97 | 123-129 | ||

1 | 7-11 | 38-43 | 70-74 | 101-106 | |||

2 | 16-20 | 48-51 | 79-83 | 111-114 | |||

3 | 26-28 | 57-60 | 89-91 | 120-123 | |||

4 | 98-100 | ||||||

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

0 | 1 | 2 | 3 | 4 | 5 | 6 | |||

-5 | 5- 10 | 88- 92 | 170-175 | 253-257 | 335-340 | ||||

-4 | 20- 25 | 102-108 | 185-190 | 267-273 | 350-355 | 432-438 | |||

-3 | 34- 41 | 117-123 | 199-206 | 282-288 | 364-371 | 447-453 | |||

-2 | 49- 56 | 131-139 | 214-221 | 296-304 | 379-386 | 461-469 | |||

-1 | 63- 72 | 146-154 | 228-237 | 311-319 | 393-402 | 476-484 | |||

0 | 0- 5 | 78- 87 | 160-170 | 243-252 | 325-335 | 408-417 | 490-500 | ||

1 | 11- 19 | 93-102 | 176-184 | 258-267 | 341-349 | 423-432 | |||

2 | 26- 34 | 109-116 | 191-199 | 274-281 | 356-364 | 439-446 | |||

3 | 42- 48 | 124-131 | 207-213 | 289-296 | 372-378 | 454-461 | |||

4 | 57- 63 | 140-145 | 222-228 | 305-310 | 387-393 | 470-475 | |||

5 | 73- 77 | 155-160 | 238-242 | 320-325 | 403-407 | 485-490 | |||

6 | 418-422 | ||||||||

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.

Next Previous Contents