The Dartboard Sequence

                
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)^2 + ... + (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.)

The (a), (b), and (c) sequences each consist of three interleaved 
arithmetic progressions.  If we designate the position of each number 
by the integers modulo 20, then the positions of the values are as
shown in the table below.

                  positions modulo 20
     values       (a)      (b)    (c)

      3k+1       -3k-3     6k     6k        k = 0 to 6
      3k+2         6k     6k+3  -3k-3       k = 0 to 6
      3k+3        6k+3   -3k-3   6k+3       k = 0 to 5

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