The problem of the difficult dartboard

The problem of the difficult dartboard

The problem is how to arrange the integers from 0 through 19 in a circle so as to maximize the sum of the absolute values of the differences between neighbours in the cyclic arrangement.

If we label the vertices of the complete 20-graph with the integers in question and define the length of each edge to be minus the absolute value of the difference between the labels of the edge's endpoints, we are asked to solve on that map the Travelling Salesman's Problem, which is notoriously untractable. The conclusion is that our problem can only be solvable thanks to the very special way in which the edge lengths have been given.

The Travelling Salesman's Problem is so hard because (among other things) the verification of a purported solution is no easier than solving the problem afresh. Knowing this, I asked myself how I could verify a purported solution to the problem of the difficult dartboard.

With $f\left( {i : 0 \leq i \land i < {20}}\right)$ a permutation of the first 20 natural numbers and ${f}{0} = {f}{20}$ ,we are asked to maximize S given by

$$ S = (\sum_ {i} M _ {i}: 0 \leq i \land i < 2 0: a b s. (f _ {i} - f _ {i} (i + 1))) $$

from now on I leave the range for i understood.

The claim that some $f$ , $f$ ’say,solves the problem boils down to the claim that the corresponding S-value, Sm say, is an upper bound for S . So we find ourselves interested in upper bounds for S ; since

(0) $\operatorname{abs}.\left( {a - b}\right) = \operatorname{abs}.a + \operatorname{abs}.b$ ,

there is hope. We observe for any $x$ (see Note)

$$ \begin{array}{l} \tilde {S} \ = {\mathrm {d e f i n i t i o n} o f S } \ (S U M i: a b s. (f _ {i} - f _ {(i + 1)})) \ \leqslant {\mathrm {p r o p e r t y} o p a b s } \ (S U M _ {1}: a b s. (f _ {i} - x) + a b s. (f _ {i + 1} - x)) \ = {f. 0 = f. 2 0 } \ 2 \cdot (\sum M i: a b s. (f _ {i} - x)) \quad (*) \ \end{array} $$

Note The introduction of $x$ reflects the fact that $S$ is expressed in differences of $p$ -values: cyclic arrangements of the integers from 10 to 39 yield the same bag of $S$ -values. Once $x$ has been introduced, we can fiddle with it so as to minimize our expression for the upper bound. (End of Note.)

Our next task is to find the lowest upper

bound that $(\ast)$ can yield. Since

$$ \frac {d}{d x} (p _ {i} - x) = \left{ \begin{array}{l l} - 1 & i p f _ {i} > x \ + 1 & i p f _ {i} < x \end{array} \right. $$

$\left( *\right)$ takes on its extreme -and indeed minimum - value if

$$ (\underline {{N}} i: f _ {i} > x) = (\underline {{N}} i: f _ {i} < x) $$

hence we choose $x = 9.5$ , and the corresponding lowest upper bound is

$$ \begin{array}{l} 2 \cdot (\sum M _ {i} \because (p _ {i} - 9. 5)) \ = {\mathrm {d e f . o f} p 3 \ 2 \cdot (\sum m _ {i} \because (i - 9. 5)) \ = {\mathrm {a r i t h m e t i c} } \ 2 0 0 \ \end{array} $$

The next question is whether there exists an $f$ for which $S = 200$ . This raises the question when in (0) the equality sign holds; it does if $a$ and $b$ are of opposite sign, i.e.

$$ a b s. (f _ {i} - f _ {i} (i + 1)) = a b s. (f _ {i} - x) + a b s. (f _ {i} (i + 1) - x) $$

if $f_{i} - x$ and $f_{i}(i + 1) - x$ are of opposite sign. For $x = 9.5$ this can be achieved if in our circular arrangement the "small" values (from 0 through 9, in arbitrary order) occur interleaved with the "large" values (from 10 through 19, in any order). There are about $9! \cdot 10!$ most difficult dartboards (which is a huge number).

PS. I noticed that the introduction of the identifiers ${pm}$ and ${Sm}$ is hardly justified,but that is what I wrote! (End of PS.)

That $(\ast)$ takes on its minimum value for $9 \leq x \wedge x \leq 10$ , I did not derive in the way shown. I "saw" that as a physicist in analogy to the "machine" that constructs the Steiner point of a triangle, i.e. the point $P$ such that

$$ P A + P B + P C $$

is minimal. Place $\Delta$ ABC on a horizontal plane, and drill three holes at A,B,and C. Let three threads be joined at P; put the other ends of the threads through the holes and attach "under the table" equal weights to them. In the case of the Steiner point the device is used to argue that PA,PB,and PC meet at angles of 120°. I could not help noticing a one-dimensional tug-of-war.

I thank Ravi Jain for drawing my attention to the problem.

Austin, 27 February 1989

p r. d. Edsger W. Dgksha Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 USA