Next Previous Contents

6. Good solutions

6.1 m = 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.2 k = 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.3 k = 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
102135 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.4 Other 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.5 Lower 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
20525676 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