The arrangement of the numbers around the circumference of a standard dart board is as shown below 20 1 18 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5 Oddly enough, no one seems to know for sure how this particular arrangement was selected. It evidently dates back at least 100 years. Some say the pattern was devised by a carpenter named Brian Gamlin in 1896, while others attribute it to someone named Thomas William Buckle in 1913, but both of these attributions are relatively recent, and neither can be traced back to a contemporary source. Also, although it's clear that the numbers are ordered to mix the large and small together, and possibly to separate numerically close values as far as possible (e.g., 20 is far from 19), no one seems to know of any simple criterion that uniquely singles out this particular arrangement as the best possible in any quantitative sense. It may be just an accident of history that this particular arrangement has been adopted as the standard dart board format. It's interesting to consider various possible criteria for choosing a circular arrangement of the first n positive integers. In order to get as "flat" a distribution as possible, we might try to minimize the sum of the squares of each k consecutive terms. For example, setting k = 3, the standard dard board sequence gives (20+1+18)^2 + (1+18+4)^2 + (18+4+13)^ + ... + (5+20+1)^2 = 20478 Apparently the standard board layout described above is called the "London" dart board, and there is another, less common, version called the "Manchester" dart board, which has the sequence 20 1 16 6 17 8 12 9 14 5 19 2 15 3 18 7 11 10 13 4 for which the sum of squares of each set of three consecutive numbers is 20454, just slightly less than the London arrangement. In contrast, if we were to arrange the numbers by just inter-weaving the largest and smallest numbers like this 20 1 19 2 18 3 17 4 16 5 15 6 14 7 13 8 12 9 11 10 the resulting sum of squares of each 3 consecutive elements is 20510, so the standard dart boards are, in this sense, more flat distributions. Needless to say, all of these arrangements are much more flat than the natural monotonic sequence 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 which has a sum of 24350. By the way, note that if the sum of the squares of every sum of three consecutive numbers for a given arrangement is S, then we can form another arrangement with the same sum simply by taking the "21-complement", i.e., subtracting each number from 21. For example, the complement of the standard London arrangement is 1 20 3 17 8 15 11 6 19 4 18 2 14 5 13 10 7 12 9 16 which has the same sum (20478) as the London arrangement. This works because if we begin with an arrangement a,b,c,d,... having the sum S = (a+b+c)^2 + (b+c+d)^2 + (c+d+e)^2 + ... and replace each of the numbers a,b,c,... with 21-a, 21-b, 21-c,... respectively, the sum S' of this complementary arrangement is S' = [(21-a)+(21-b)+(21-c)]^2 + [(21-b)+(21-c)+(21-d)]^2 + ... = [63-(a+b+c)]^2 + [63-(b+c+d)]^2 + ... = S + 20(63)^2 - 2(63)[(a+b+c)+(b+c+d)+...] Each of the numbers from 1 to 20 appears three times in the summation inside the square brackets in the last term, so that summation equals 630, and hence S' = S. (The same identity applies to the N+1 complement for sums of squares of every sum of k consecutive terms of a circular arrangement of the first N integers.) How would we go about finding the circular arrangement of the integers 1 to 20 that gives the smallest sum of squares of every sum of three consecutive numbers? One possible approach would be to begin with the monotonic arrangement and then check each possible transposition of two numbers to see which one gives the lowest result. Then make that change and repeat the process, at each stage always choosing the transposition that gives the steepest reduction in the sum. This "greedy algorithm" produces arrangements with the following sums (of squares of each 3 consecutive terms around the cycle): 24350 21650 20678 20454 20230 20110 19990 19970 19950 19946 19938 19936 19930 19926 19918 Once it reaches the arrangement with the sum 19918, no further transposition of two numbers gives any reduction in the sum. Of course, this doesn't imply that 19918 is the minimum possible sum, it simply means that it is a "local" minimum. We might try to make our search algorithm more robust by considering all possible permutations of THREE numbers at each stage. (This includes permutations of two, since some of the permutations of three numbers leave one of the numbers fixed.) Applying the greedy algorithm to permutations of any three numbers gives dartboard arrangements with the sums 24350 21542 20362 20098 19978 19954 19942 19930 Once we reach 19930, no further permutation of three numbers gives any reduction in the sum. Interestingly, this doesn't even produce as low a result as the simple transpositions, and it illustrates the fact that a local minimum need not be a global minimum. By applying permutations of three elements, the algorithm is too greedy and enters a region of the configuration space that cannot be extended by such permutations, whereas the transpositions follow a less-steep path that leads them ultimately to a lower level. Expanding our algorithm to examine all permutations of FOUR numbers, we get a sequence of dartboard arrangements with the following sums: 24350 20678 20190 19974 19932 19918 19910 19908 19902 19900 19896 19894 Thus we arrive at the lowest sum we've seen so far, but of course this is still just a local minimum, with no guarantee that it is the lowest possible sum. Expanding our algorithm to take the best of all the permutations of FIVE number at each stage, we get the sequence of dartboard arrangements 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 6 2 19 4 5 16 7 8 9 10 11 12 13 14 15 3 17 18 1 20 1 2 19 9 5 18 7 8 16 10 11 12 4 14 15 3 17 13 1 20 10 2 19 9 5 18 7 8 16 6 11 15 4 14 13 3 17 12 1 20 These arrangements have the sums 24350, 20406, 19992, and 19874 respectively. By applying various combinations of these algorithms to various initial arrangements, we can often arrive at the ultimate sum 19874, but never to any lower sum. However, there appear to be three distinct arrangements with this sum (up to rotations and reflections). Each of them has 1 adjacent to 20, so to compare the arrangements directly we will rotate and reflect them if necessary so that they begin with 20 and 1. With this convention, the three minimal sequences, labeled (a), (b), and (c), are (a) 20 1 11 19 2 12 16 3 14 13 5 15 10 6 17 7 8 18 4 9 (b) 20 1 11 18 2 13 15 4 14 12 5 16 9 7 17 6 8 19 3 10 (c) 20 1 12 17 3 13 14 4 15 11 6 16 8 7 18 5 9 19 2 10 The differences between the (a) and (b) sequences, and between the (c) and (b) sequences, are shown below: 0 0 0 1 0 -1 1 -1 0 1 0 -1 1 -1 0 1 0 -1 1 -1 0 0 1 -1 1 0 -1 0 1 -1 1 0 -1 0 1 -1 1 0 -1 0 Interestingly, if we reverse the order of the lower differences and then rotate two places to the right, the result is exactly the negative of the upper differences. This is because the (a) and (c) arrangements are the 21-complements of each other (as defined above). The (b) arrangement is "self-dual", i.e., it is its own complement. We also note that (a) and (b) differ by the transpositions (3,4) (6,7) (9,10) (12,13) (15,16) (18,19) whereas (b) and (c) differ by the transpositions (3,2) (6,5) (9,8) (12,11) (15,14) (18,17) Thus the three minimal sequences differ from each other by permutations of six numbers, and no permutations of just five or fewer numbers can transform one of these to the others using the greedy algorithm, if we require the sum to drop or remain constant on each permutation. But if we allow permutations of six numbers it becomes possible to oscillate between these three arrangements in steps with constant sums. This is an interesting example of "symmetry breaking". At lower "energies" (permutations of fewer terms) every sequence of arrangements progresses to one of several different possible stable limiting arrangements, but at higher "energies" (permutations of more terms) these asymptotic arrangements can transform into each other, so the sequence can oscillate between them. (Of course, if we allow permutations of all 20 terms at once, then any arrangement can be transformed to any other in a single step.) Despite the extensive numerical evidence, and the apparently unique symmetry of the (a), (b), and (c) arrangements, one could still question whether our search algorithm based on permutations of five elements is guaranteed to find the global minimum. To prove that the three arrangements (a),(b),(c) presented above are indeed the absolute minimal solutions, note that the sum of the sums of three consecutive elements must be 630, which is three times the sum of the integers from 1 to 20. If we didn't require integer values, the minimal solution would be given by uniformly distributing this, so each sum of three consecutive terms would be 31.5, but since we require integer values, this is ruled out. We could consider arrangements such that every sum of three consecutive terms is either 31 or 32, but it's easy to see that this cannot lead to an acceptable solution. Notice that the two consecutive 3-sums for the four elements n1,n2,n3,n4 are n1+n2+n3 and n2+n3+n4, so if the two 3-sums are equal, it follows that n4=n1, and hence this is not an acceptable solution (the 20 elements are distinct). Similarly we can show that two 3-sums can't alternate more than twice. Hence the flattest possible arrangements that are not ruled out by these simple considerations must have more than two distinct values for the 3-sums Indeed the solutions with 19874 consist of the 3-sum values 30, 31, 32, and 33 with valences 6,4,4,6 respectively. These 3-sums for the (a), (b) and (c) arrangements are as shown below (a) 32 31 32 33 30 31 33 30 32 33 30 31 33 30 32 33 30 31 33 30 (b) 32 30 31 33 30 32 33 30 31 33 30 32 33 30 31 33 30 32 33 31 (c) 33 30 32 33 30 31 33 30 32 33 30 31 33 30 32 33 30 31 32 31 By examining each sequence of the values 30, 31, 32, and 33, checking to see which ones correspond to 3-sums of the integers 1 to 20, we find that indeed the only viable sequences are those corresponding to the arrangements (a), (b), and (c). Thus these are the circular arrangements of the integers 1 through 20 such that the sum of squares of every 3 consecutive terms has the smallest possible value, namely 19874. (If we evaluate the sum of squares of every three consecutive elements of these 3-sum sequences we find that they yield 178614, 178618, and 178614 respectively.) By the way, to find the arrangement that maximizes (rather than minimizes) the sum, it's fairly intuitive that we would cluster the largest numbers together as tightly as possible. This leads to the arrangement 20 19 17 15 13 11 9 7 5 3 1 2 4 6 8 10 12 14 16 18 which has the sum 25406. Indeed this is the highest sum I've found using the greedy algorithm with permutations of 2, 3, 4, and 5 elements (selecting the highest rather than the lowest at each stage), although it's interesting that there are many initial arrangements from which this algorithm does not lead to this global maximum. In general if H(n,k) and L(n,k) are the highest and lowest sums of squares of every k consecutive elements in a circular arrangement of the first n positive integers, are the values of H(n,k) and L(n,k) well known and/or easily computed? Another possible way of "optimizing" the arrangement of the numbers 1 through 20 on a dart board would be to minimize the sum of the squares of every sum of TWO (rather than three) consecutive numbers. In general, I think the minimum sum of squares of every sum of two consecutive numbers in a cyclical arrangement of the integers 1 through N is S_min(N) = N^3 + 2N^2 + 2N - j where j is 1 if N is odd, and j is 2 if N is even. For the particular case N=20 this formula gives a minimum sum of 8838. For even N the minimum arrangement has the odd and even numbers restricted to separate halfs of the cycle, as illustrated below for N=20 1 3 5 7 9 10 8 6 4 2 19 17 15 13 11 12 14 16 18 20 For odd N the minimum arrangement is very simple, as shown below for N=19. 1 3 5 7 9 11 13 15 17 19 18 16 14 12 10 8 6 4 2 This raises some interesting questions. Given any circular arrangement of the integers 0 through n-1, let S denote the sum of squares of every sum of two contiguous numbers, and let v(n) denote the number of distinct values of S for all n! possible arrangements. Following is a table of the number of distinct values of v(n) n v(n) ----- --------- 1 1 2 1 3 1 4 3 5 8 6 21 7 43 8 69 9 102 10 145 Hugh Montgomery, A. M. Odlyzko, and Bjorn Poonen developed a very nice approach to this problem, showing that the general term with n>6 is given by / (n^3 - 16n + 27)/6 if n is odd v(n) = ( \ (n^3 - 16n + 30)/6 if n is even A whole family of interesting sequences can be produced by generalizing the definition as follows: Given any circular arrangement of the integers 0 through n-1, let S denote the sum of the qth powers of every sum of k contiguous numbers. Then let v(q,k,n) denote the number of distinct values of S for all possible arrangements. With this nomenclature, the previous sequence is denoted as v(2,2,n). Of course, we have v(1,k,n) = 1 for all k and n, because the sum of the 1st powers is independent of the arrangement. We also have v(q,1,n) = 1 because the sum of any fixed power of the individual numbers is also independent of the arrangement. Also, for fixed values of q and n, the function v is PERIODIC in k. Another generalization is to add some constant integer j to each of the numbers 0 to n-1. Thus, the general function has four indices, v(q,k,j,n). Notice that v is independent of j for q<3, but for larger values of q, j becomes significant. Can v(q,k,j,n) be expressed in closed form as a function of the indices? Which other integer sequences are contained in this family? Which continuous functions (e.g., sin(x), cos(x), exp(x), etc) can be approximated by sequences of this form?

Return to MathPages Main Menu