Question

Nine balls, numbered 1, 2, … ,9 are put randomly at 9 equally spaced points on a circle, each point with a ball. Let S be the sum of the absolute values of the differences of the numbers of all two neighboring balls. The number of ways such that S has the minimum possible value is

Answer 1

18

Answer 2

Let the nine points on the circle be $P_1, P_2, \dots, P_9$ in clockwise order. Let $x_i$ be the number on the ball at point $P_i$. The set $\{x_1, x_2, \dots, x_9\}$ is a permutation of $\{1, 2, \dots, 9\}$. The sum $S$ is given by $S = \sum_{i=1}^9 |x_i - x_{i+1}|$, where $x_{10} = x_1$.

We can rewrite the sum $S$ by considering the contribution of each unit interval $(j, j+1)$ for $j \in \{1, 2, \dots, 8\}$. The term $|x_i - x_{i+1}|$ represents the number of unit intervals between $x_i$ and $x_{i+1}$. The sum $S$ is the total number of times the segments $(x_i, x_{i+1})$ cross the boundaries between consecutive integers on the number line.

Let $C_j$ be the number of times the boundary between the set $\{1, 2, \dots, j\}$ and $\{j+1, \dots, 9\}$ is crossed by the path $x_1 \to x_2 \to \dots \to x_9 \to x_1$. An edge $(x_i, x_{i+1})$ crosses this boundary if one endpoint is in $\{1, \dots, j\}$ and the other is in $\{j+1, \dots, 9\}$.

Since the path is a closed loop, the number of times it enters the set $\{j+1, \dots, 9\}$ from $\{1, \dots, j\}$ must equal the number of times it enters $\{1, \dots, j\}$ from $\{j+1, \dots, 9\}$. Thus, $C_j$ must be an even number for every $j \in \{1, 2, \dots, 8\}$.

The sum $S = \sum_{j=1}^8 C_j$. To minimize $S$, we must minimize each $C_j$. The minimum possible value for an even number is 2.

If $C_j = 2$ for all $j=1, \dots, 8$, the sum $S = \sum_{j=1}^8 2 = 8 \times 2 = 16$.

Let's check if $S=16$ is achievable.

Consider the arrangement where the numbers are in increasing order: $1, 2, 3, 4, 5, 6, 7, 8, 9$. The differences are $|1-2|=1, |2-3|=1, \dots, |8-9|=1$, and $|9-1|=8$. The sum is $8 \times 1 + 8 = 16$.

In this arrangement, for any $j \in \{1, \dots, 8\}$, the set $\{1, \dots, j\}$ is $1, 2, \dots, j$ and the set $\{j+1, \dots, 9\}$ is $j+1, \dots, 9$. The path $1 \to 2 \to \dots \to j \to j+1 \to \dots \to 9 \to 1$ crosses the boundary between $\{1, \dots, j\}$ and $\{j+1, \dots, 9\}$ at two points: the edge $(j, j+1)$ and the edge $(9, 1)$. So $C_j=2$ for all $j$. This confirms that the minimum value of $S$ is 16.

We need to find the number of arrangements such that $S=16$.

The condition $S=16$ is equivalent to $C_j=2$ for all $j=1, \dots, 8$.

$C_j=2$ means that the numbers $\{1, \dots, j\}$ and $\{j+1, \dots, 9\}$ must be arranged in two contiguous blocks on the circle. For example, $x_1, \dots, x_j$ are a permutation of $\{1, \dots, j\}$ and $x_{j+1}, \dots, x_9$ are a permutation of $\{j+1, \dots, 9\}$. The edges crossing the boundary are $(x_j, x_{j+1})$ and $(x_9, x_1)$.

Consider the arrangement $x_1, x_2, \dots, x_9$.

If $C_j=2$ for all $j$, then the set $\{1, \dots, j\}$ must occupy $j$ consecutive positions on the circle for each $j$.

For $j=1$, $\{1\}$ must be in a block of size 1. This doesn't say much.

For $j=8$, $\{1, \dots, 8\}$ must be in a block of size 8. This means the numbers $1, \dots, 8$ must occupy 8 consecutive positions, and 9 occupies the remaining position.

Let the positions be $P_1, \dots, P_9$. Suppose 9 is at $P_1$. Then $P_2, \dots, P_9$ must be occupied by a permutation of $1, \dots, 8$. The edges crossing the boundary between $\{1, \dots, 8\}$ and $\{9\}$ are $(x_9, x_1)$ and $(x_1, x_2)$. So $|x_9 - x_1| + |x_1 - x_2| = |x_9-9| + |9-x_2|$.

If 9 is at $P_1$, then $x_1=9$. The neighbors are $x_9$ and $x_2$. Both $x_9, x_2 \in \{1, \dots, 8\}$.

The sum of differences is $|x_1-x_2| + |x_2-x_3| + \dots + |x_8-x_9| + |x_9-x_1|$.

With $x_1=9$, $S = |9-x_2| + |x_2-x_3| + \dots + |x_8-x_9| + |x_9-9|$.

The remaining numbers $x_2, \dots, x_9$ are a permutation of $\{1, \dots, 8\}$.

The sum of differences $|x_2-x_3| + \dots + |x_8-x_9|$ is the sum of differences for an open chain of 7 numbers from $\{1, \dots, 8\}$.

Let $y_1=x_2, y_2=x_3, \dots, y_8=x_9$. $\{y_1, \dots, y_8\}$ is a permutation of $\{1, \dots, 8\}$.

$S = |9-y_1| + \sum_{i=1}^7 |y_i - y_{i+1}| + |y_8-9|$.

We know $S=16$.

$|9-y_1| + \sum_{i=1}^7 |y_i - y_{i+1}| + |y_8-9| = 16$.

Since $y_i \in \{1, \dots, 8\}$, $|9-y_1| = 9-y_1$ and $|9-y_8| = 9-y_8$.

$18 - (y_1+y_8) + \sum_{i=1}^7 |y_i - y_{i+1}| = 16$.

$\sum_{i=1}^7 |y_i - y_{i+1}| = y_1+y_8 - 2$.

The sequence $y_1, \dots, y_8$ is a permutation of $1, \dots, 8$. This is an open chain.

The sum of differences for an open chain $y_1, \dots, y_m$ which is a permutation of $1, \dots, m$ is $\sum_{i=1}^{m-1} |y_i - y_{i+1}|$. This sum is minimized when the sequence is monotonic (increasing or decreasing).

For $y_1, \dots, y_8$ being a permutation of $1, \dots, 8$, the minimum value of $\sum_{i=1}^7 |y_i - y_{i+1}|$ is $8-1=7$, achieved by $1, 2, \dots, 8$ or $8, 7, \dots, 1$.

If $y_1, \dots, y_8$ is $1, 2, \dots, 8$, sum is 7. $y_1=1, y_8=8$. $y_1+y_8-2 = 1+8-2=7$. This matches.

If $y_1, \dots, y_8$ is $8, 7, \dots, 1$, sum is 7. $y_1=8, y_8=1$. $y_1+y_8-2 = 8+1-2=7$. This matches.

So, if 9 is at $P_1$, the numbers $x_2, \dots, x_9$ must be $1, 2, \dots, 8$ in order, or $8, 7, \dots, 1$ in order.

Arrangement 1: $x_1=9$, $x_2=1, x_3=2, \dots, x_9=8$. Sequence: $9, 1, 2, 3, 4, 5, 6, 7, 8$.

Differences: $|9-1|+|1-2|+|2-3|+\dots+|7-8|+|8-9| = 8+1+1+1+1+1+1+1+1 = 8+8=16$. This works.

Arrangement 2: $x_1=9$, $x_2=8, x_3=7, \dots, x_9=1$. Sequence: $9, 8, 7, 6, 5, 4, 3, 2, 1$.

Differences: $|9-8|+|8-7|+\dots+|2-1|+|1-9| = 1+1+1+1+1+1+1+1+8 = 8+8=16$. This works.

So, for a fixed position of 9 (say $P_1$), there are 2 possible arrangements for the other numbers.

The number 9 can be placed at any of the 9 positions.

If 9 is at $P_i$, then its neighbors $x_{i-1}$ (or $x_9$ if $i=1$) and $x_{i+1}$ (or $x_1$ if $i=9$) must be the ends of a monotonic sequence of the numbers $\{1, \dots, 8\}$ arranged in the remaining 8 positions.

Let 9 be at $P_1$. The sequence is $9, x_2, \dots, x_9$. $\{x_2, \dots, x_9\}$ is a permutation of $\{1, \dots, 8\}$.

The sequence $x_2, x_3, \dots, x_9$ must be $1, 2, \dots, 8$ or $8, 7, \dots, 1$.

This gives $9, 1, 2, 3, 4, 5, 6, 7, 8$ and $9, 8, 7, 6, 5, 4, 3, 2, 1$.

These arrangements are considered distinct if they are different when read from $P_1$ clockwise.

Let's fix the position $P_1$. There are 9 choices for the number at $P_1$.

If $x_1=9$, then $x_2, \dots, x_9$ must be $1, 2, \dots, 8$ or $8, 7, \dots, 1$. This gives 2 arrangements starting with 9 at $P_1$.

$9, 1, 2, 3, 4, 5, 6, 7, 8$

$9, 8, 7, 6, 5, 4, 3, 2, 1$

What if $x_1=1$? Then its neighbors $x_9, x_2$ must be the ends of a monotonic sequence of $2, \dots, 9$.

The remaining numbers $x_2, \dots, x_9$ are a permutation of $\{2, \dots, 9\}$.

$S = |1-x_2| + |x_2-x_3| + \dots + |x_8-x_9| + |x_9-1| = 16$.

Since $x_i \in \{2, \dots, 9\}$ for $i=2, \dots, 9$, $|1-x_2|=x_2-1$ and $|x_9-1|=x_9-1$.

$(x_2-1) + \sum_{i=2}^8 |x_i - x_{i+1}| + (x_9-1) = 16$.

$\sum_{i=2}^8 |x_i - x_{i+1}| = 18 - (x_2+x_9)$.

Let $y_1=x_2, \dots, y_8=x_9$. $\{y_1, \dots, y_8\}$ is a permutation of $\{2, \dots, 9\}$.

The minimum value of $\sum_{i=1}^7 |y_i - y_{i+1}|$ for a permutation of $\{2, \dots, 9\}$ is $(9-2) = 7$, achieved by $2, 3, \dots, 9$ or $9, 8, \dots, 2$.

If $y_1, \dots, y_8$ is $2, 3, \dots, 9$, sum is 7. $y_1=2, y_8=9$. $18-(y_1+y_8) = 18-(2+9)=7$. This matches.

If $y_1, \dots, y_8$ is $9, 8, \dots, 2$, sum is 7. $y_1=9, y_8=2$. $18-(y_1+y_8) = 18-(9+2)=7$. This matches.

So, if $x_1=1$, the sequence $x_2, \dots, x_9$ must be $2, 3, \dots, 9$ or $9, 8, \dots, 2$.

Arrangement 3: $1, 2, 3, 4, 5, 6, 7, 8, 9$. Differences: 1, 1, ..., 1, 8. Sum = 16.

Arrangement 4: $1, 9, 8, 7, 6, 5, 4, 3, 2$. Differences: 8, 1, ..., 1, 1. Sum = 16.

In general, the minimum sum $S=16$ is achieved when the numbers are arranged in an almost monotonic sequence.

The sequence must be of the form $k, k+1, \dots, 9, 1, 2, \dots, k-1$ or its reverse, but with one break in monotonicity.

The arrangements that achieve the minimum sum are those where the numbers $1, 2, \dots, 9$ are placed consecutively around the circle, either in increasing or decreasing order.

Sequence 1: $1, 2, 3, 4, 5, 6, 7, 8, 9$. The sum is $|1-2|+|2-3|+\dots+|8-9|+|9-1| = 1 \times 8 + 8 = 16$.

Sequence 2: $9, 8, 7, 6, 5, 4, 3, 2, 1$. The sum is $|9-8|+|8-7|+\dots+|2-1|+|1-9| = 1 \times 8 + 8 = 16$.

Any cyclic shift of these sequences is considered a different arrangement on the fixed points $P_1, \dots, P_9$.

From sequence 1:

$1, 2, 3, 4, 5, 6, 7, 8, 9$

$2, 3, 4, 5, 6, 7, 8, 9, 1$

...

$9, 1, 2, 3, 4, 5, 6, 7, 8$

There are 9 such cyclic shifts. All of them result in $S=16$.

From sequence 2:

$9, 8, 7, 6, 5, 4, 3, 2, 1$

$8, 7, 6, 5, 4, 3, 2, 1, 9$

...

$1, 9, 8, 7, 6, 5, 4, 3, 2$

There are 9 such cyclic shifts. All of them result in $S=16$.

Are there any overlaps between the two sets of arrangements?

The first set consists of sequences like $(k, k+1, \dots, 9, 1, \dots, k-1)$.

The second set consists of sequences like $(k, k-1, \dots, 1, 9, \dots, k+1)$.

For example, $1, 2, \dots, 9$ (from set 1 with $k=1$) and $1, 9, 8, \dots, 2$ (from set 2 with $k=1$). These are different sequences.

The sequence $1, 2, \dots, 9$ is not a cyclic shift of $9, 8, \dots, 1$.

The sequence $1, 2, 3, \dots, 9$ has differences (1, 1, 1, 1, 1, 1, 1, 1, 8).

The sequence $9, 8, 7, \dots, 1$ has differences (1, 1, 1, 1, 1, 1, 1, 1, 8).

The cyclic shifts of $1, 2, \dots, 9$ are $1, 2, \dots, 9$; $2, 3, \dots, 9, 1$; ...; $9, 1, \dots, 8$.

The cyclic shifts of $9, 8, \dots, 1$ are $9, 8, \dots, 1$; $8, 7, \dots, 1, 9$; ...; $1, 9, \dots, 2$.

These two sets of sequences are distinct. For example, the sequence $1, 2, 3, 4, 5, 6, 7, 8, 9$ increases initially, while $9, 8, 7, 6, 5, 4, 3, 2, 1$ decreases initially. A cyclic shift preserves the relative order of elements (up to the wrap-around). So a cyclic shift of an increasing sequence (with one large drop) is still an increasing sequence (with one large drop). A cyclic shift of a decreasing sequence (with one large rise) is still a decreasing sequence (with one large rise).

Thus, the 9 cyclic shifts of $1, 2, \dots, 9$ are distinct from the 9 cyclic shifts of $9, 8, \dots, 1$.

Total number of ways = 9 (cyclic shifts of $1, 2, \dots, 9$) + 9 (cyclic shifts of $9, 8, \dots, 1$) = 18.

These are arrangements on fixed points. If the points are not fixed, we would divide by rotations and reflections. But the question says "put randomly at 9 equally spaced points on a circle, each point with a ball", implying the points are distinguishable.

The number of ways to arrange the balls on the 9 fixed points is the number of permutations of $\{1, \dots, 9\}$ that result in $S=16$.

These are the 18 sequences described above.

Example arrangements:

$P_1, P_2, ..., P_9$

$1, 2, 3, 4, 5, 6, 7, 8, 9$ (S=16)

$9, 1, 2, 3, 4, 5, 6, 7, 8$ (S=16)

...

$9, 8, 7, 6, 5, 4, 3, 2, 1$ (S=16)

$1, 9, 8, 7, 6, 5, 4, 3, 2$ (S=16)

...

Total number of arrangements = 18.