Next Previous Contents

## 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.

 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