Next Previous Contents

## 6.1m = 2

 k L(k,2) # all optimal solutions 0 0 1 1 2 1 1 2 6 1 2 3 3 10 3 1 5 8 / 2 4 5 / 3 4 5 4 16 3 1 2 8 13 / 4 6 7 9 / 3 6 7 8 5 24 1 4 8 10 11 13 6 32 2 4 8 12 14 15 17 / 5 7 12 13 15 16 7 40 8 2 4 5 19 20 31 32 / 2 11 13 14 18 19 21 / 2 13 14 16 17 22 23 / 4 8 12 16 18 19 21 / 5 10 15 17 18 19 21 / 5 11 13 17 19 20 40 / 6 12 15 16 17 19 20 / 7 9 15 17 19 20 40 8 52 3 2 4 6 7 25 26 41 42 / 5 8 19 20 22 23 29 55 / 6 12 18 21 22 23 25 26 9 64 2 2 4 6 8 9 31 32 51 52 / 6 12 18 24 27 28 29 31 32 10 76 2 2 4 6 8 10 11 37 38 61 62 / 6 12 18 24 30 33 34 35 37 38

### Patterns

A) The set {2,4,...,2t,2t+1} shows that t+1 coins can reach 4t+2 (for t>=0), that is, 4k-2. This is optimal for k=1,2,3.

B) The set {4,8,12,...,4t,4t+2,4t+3,4t+5} shows that t+3 coins can reach 8t+8 (for t>0), that is, 8k-16. This is optimal for k=4,5,6,7.

C) The set {2,4,6,...,2t,2t+1,6t+7,6t+8,10t+11,10t+12} shows that t+5 coins can reach 12t+16 (for t>0), that is, 12k-44. This is optimal for k=7,8,9,10.

D) The set {6,12,18,...,6t,6t+3,6t+4,6t+5,6t+7,6t+8} shows that t+5 coins can reach 12t+16 (for t>0), just like the previous.

### Asymptotics

With k coins one cannot get more than k(k+1) (there are k(k-1) sums and differences, and 2k single values taken once or twice). Equality holds for k=0,1,2 and for no other values of k.

An easy lower bound is found by taking the set {1,2,...,t,3t+1,5t+2,7t+3,...,(2a+1)t+a}. It shows that t+a coins can reach (2a+2)t+a, that is, that k coins can reach 2a(k-a)+2k-a. This is largest for a=[k/2] and then yields k(k+3)/2.

Tim Peeters finds a slightly better solution by taking the consecutive part at the end instead of the beginning: the set {x,2x,...,tx,tx+1,...,tx+x-1} of size t+x-1 reaches 2(tx+x-1). This is maximal for x = 1 + k/2 (rounded up or down) and then yields L(k,2) >= [k(k+4)/2].

## 6.2k = 3

 m L(3,m) # all optimal solutions 1 3 1 1 2 3 2 10 3 1 5 8 / 2 4 5 / 3 4 5 3 24 2 1 8 11 / 5 7 8 4 46 1 9 10 16 5 80 1 8 17 23 6 129 1 9 31 32 7 196 1 11 38 39 8 277 1 13 45 46 9 372 1 15 52 53 10 500 1 15 82 83 11 660 1 17 93 94 12 842 1 19 104 105 13 1046 1 21 115 116 14 1272 1 23 126 127 15 1560 1 23 172 173 16 1883 1 25 187 188 17 2236 1 27 202 203 18 2619 1 29 217 218 19 3040 1 29 275 276 20 3544 1 31 294 295 21 4086 1 33 313 314 22 4666 1 35 332 333 23 5284 1 37 351 352 24 5969 1 37 425 426 25 6740 1 39 448 449 26 7557 1 41 471 472 27 8420 1 43 494 495 28 9329 1 45 517 518 29 10342 1 45 607 608 30 11436 1 47 634 635

Each of these was found to be best possible by exhaustive search.

For a discussion, see above.

## 6.3k = 4

 m L(4,m) # all optimal solutions 1 4 1 1 2 3 4 2 16 3 1 2 8 13 / 3 6 7 8 / 4 6 7 9 3 47 1 11 12 15 20 4 104 1 1 5 34 47 5 207 1 1 7 68 93 6 375 1 1 7 93 118 7 624 1 1 9 155 196 8 984 1 1 9 196 237 9 1475 1 1 11 294 355 10 2135 1 1 11 355 416

(These values are from Jurgen van Dijk. Am not sure whether he claims optimality. I found the same values for m <= 7. For m=8,9,10 they are optimal among the sets containing 1.)

## 6.4Other exact values

The following values were found by Jurgen van Dijk.

 k m L(k,m) # all optimal solutions 5 3 73 1 5 18 30 33 34 5 4 189 1 3 5 17 93 148 6 3 110 1 14 22 25 26 55 57

(I also found L(5,3) = 73 and L(6,3) = 110. The 73 is optimal. The 110 is probably optimal: any nonlisted solutions have w_6 >= 119. Have not verified the 189.)

## 6.5Lower bounds

It is fairly easy to come up with good solutions, while it takes a long time to prove optimality. For example, finding the four solutions

 k m L # solutions 11 2 90 4 4 8 12 16 18 19 21 62 63 68 69 8 16 24 30 32 35 39 41 42 44 45 8 16 24 32 36 38 41 42 43 45 47 8 16 24 32 36 38 41 42 45 47 51

takes only a few seconds, but proving optimality takes many hours. (I think I did this, but cannot find my notes anymore, so to stay on the safe side I only list them here as good solutions.)

A few lower bounds for m=3 (and one for m=5) found by Wil van der Aalst and Ton Weijters using a genetic search:

 k m L solution(s) 7 3 153 19 38 40 46 47 50 51 8 3 210 19 38 57 59 65 66 69 70 9 3 276 3 6 7 8 25 79 134 187 239 / 4 8 12 53 71 108 117 131 140 10 3 336 2 4 7 17 18 30 94 159 233 296 20 5 25676 1282 2387 3552 3810 3955 4073 4223 4355 4472 45534683 4787 4907 5022 5159 5217 5306 5431 5557 5592

I found the same solutions for 153 and 210 using different heuristics. However, the 153 is not best possible - I also found a solution with 160:

 k m L solution 7 3 160 4 12 38 58 68 77 79

Added 2004-03-14: Tommi Vainikainen writes that he improved the 210 to 217:

 k m L solution 8 3 217 5 8 12 14 62 101 150 189

Next Previous Contents