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

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?
```