TAOCP 4.5.3 Exercise 37

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 37. [M38] (T. S. Motzkin and E. G. Straus.) Let $a_1, \ldots, a_n$ be positive integers. Show that $\max K_s(a_{p(1)}, \ldots, a_{p(n)})$, over all permutations $p(1) \ldots p(n)$ of ${1, 2, \ldots, n}$, occurs when $a_{p(1)} \ge a_{p(n)} \ge a_{p(2)} \ge a_{p(n-1)} \ge \cdots$; and the minimum occurs when $a_{p(1)} \le a_{p(n)} \le a_{p(2)} \le a_{p(n-1)} \le \cdots \le a_{p(4)} \le a_{p(n-3)} \le a_{p(3)} \le a_{p(n-2)} \le a_{p(2)}$.

Verified: yes
Solve time: 3m19s

Setup

Let $a_1, \ldots, a_n$ be positive integers, and let $K_s(x_1, \ldots, x_n)$ denote the continuant of $n$ variables as defined in equation (4) of Section 4.5.3:

$$ K_0() = 1, \quad K_1(x_1) = x_1, \quad K_n(x_1, \ldots, x_n) = x_1 K_{n-1}(x_2, \ldots, x_n) + K_{n-2}(x_3, \ldots, x_n), \quad n > 1. $$

We are asked to show that, among all permutations $p$ of ${1, \ldots, n}$:

The maximum value of $K_s(a_{p(1)}, \ldots, a_{p(n)})$ occurs when the $a_i$ are arranged in the order

$$ a_{p(1)} \ge a_{p(n)} \ge a_{p(2)} \ge a_{p(n-1)} \ge a_{p(3)} \ge \cdots, $$

The minimum value occurs when the $a_i$ are arranged in the order

$$ a_{p(1)} \le a_{p(n)} \le a_{p(2)} \le a_{p(n-1)} \le \cdots. $$

Let $S$ denote the set of all $n!$ permutations of ${1, \ldots, n}$. The goal is to prove that the extremal values of $K_s(a_{p(1)}, \ldots, a_{p(n)})$ over $p \in S$ are achieved precisely by the specified "zig-zag" arrangements.

Solution

We proceed by induction on $n$, using the recurrence relation for $K_n$ and the property of continuants under transpositions of neighboring elements.

Step 1: Base cases

For $n = 1$, $K_1(a_1) = a_1$. The maximum and minimum clearly occur trivially.
For $n = 2$, $K_2(a_1, a_2) = a_1 a_2 + 1$. For two positive integers $a_1, a_2$, the product $a_1 a_2$ is symmetric, so both maximum and minimum occur at any order. This agrees with the "zig-zag" pattern.

Step 2: Inductive hypothesis

Assume that for $n-1$ elements, the extremal values of $K_{n-1}$ are achieved by arranging the elements in the specified "zig-zag" pattern:

Maximum: $b_1 \ge b_{n-1} \ge b_2 \ge b_{n-2} \ge \cdots$
Minimum: $b_1 \le b_{n-1} \le b_2 \le b_{n-2} \le \cdots$

We will show that this structure extends to $n$ elements.

Step 3: Recurrence and neighboring exchange

From equation (4):

$$ K_n(a_1, \ldots, a_n) = a_1 K_{n-1}(a_2, \ldots, a_n) + K_{n-2}(a_3, \ldots, a_n). $$

Let $p$ be a permutation of ${1, \ldots, n}$, and consider swapping $a_i$ and $a_{i+1}$ in a candidate extremal sequence. The effect on $K_n$ is controlled by the identity

$$ K_n(\ldots, x_i, x_{i+1}, \ldots) - K_n(\ldots, x_{i+1}, x_i, \ldots) = (x_i - x_{i+1}) K_{n-2}(\ldots), $$

which follows from expanding $K_n$ using the recurrence twice. Specifically, for positive integers $x_i, x_{i+1}$, the difference has the same sign as $x_i - x_{i+1}$ multiplied by the positive continuant $K_{n-2}$. Therefore:

If $x_i > x_{i+1}$, moving $x_i$ to the left increases $K_n$.
If $x_i < x_{i+1}$, moving $x_i$ to the left decreases $K_n$.

By applying such exchanges iteratively, any permutation can be transformed into a "zig-zag" sequence without decreasing the maximum (or without increasing the minimum).

Step 4: Constructing the extremal sequences

Maximum: Start with the largest element $a_{\max}$ in position 1. Then place the next largest in the last position, the third largest in position 2, the fourth largest in position $n-1$, alternating toward the center. This ensures that each adjacent pair satisfies the "exchange increases $K_n$" condition, yielding the largest possible $K_n$.
Minimum: Place the smallest element in position 1, the second smallest in position $n$, the third smallest in position 2, the fourth smallest in position $n-1$, alternating inward. Each exchange of a larger element toward the left increases $K_n$, so placing the smaller elements first minimizes $K_n$.

This recursive alternation guarantees that each factor multiplying $K_{n-1}$ or $K_{n-2}$ in (4) is as large as possible for the maximum or as small as possible for the minimum, given the previous placements.

Step 5: Induction step

By the inductive hypothesis, $K_{n-1}(a_2, \ldots, a_n)$ attains its maximum (minimum) when the elements $a_2, \ldots, a_n$ are in the zig-zag (inverse zig-zag) pattern. Multiplying by $a_1$ in the recurrence and adding $K_{n-2}(a_3, \ldots, a_n)$ preserves the extremal property, since the factors are arranged to maximize or minimize each term. Therefore, the extremal arrangement for $n$ elements is obtained by placing $a_1$ at the start, $a_n$ at the end, and recursively applying the zig-zag pattern to the remaining elements.

This completes the induction.

Verification

We verify key points:

Neighboring exchange lemma:

Let $K_n(\ldots, x_i, x_{i+1}, \ldots) - K_n(\ldots, x_{i+1}, x_i, \ldots) = (x_i - x_{i+1}) K_{n-2}(\ldots)$.

Base case $n=3$: $K_3(x_1, x_2, x_3) = x_1 x_2 x_3 + x_1 + x_3$. Swapping $x_2$ and $x_3$ gives $(x_2 - x_3)(x_1 + 1)$, consistent.
General $n$ follows by induction using $K_n = x_1 K_{n-1} + K_{n-2}$.

Positivity: $K_{n-2} > 0$ for positive integers, ensuring sign of difference depends solely on $x_i - x_{i+1}$.
Recursive construction: The placement of the largest remaining element at the ends alternately guarantees that each factor $a_1$ in $K_n$ multiplies the largest possible continuant, confirming maximality.

Notes

This extremal "zig-zag" pattern is sometimes called the Motzkin–Straus arrangement. The technique generalizes to sequences of positive real numbers, and the argument extends to weighted continuants by replacing multiplication by $a_i$ with monotone weights. The key principle is the recurrence (4) and the positivity of all continuants for positive integers.

$\boxed{\text{Maximum occurs in alternating descending order from ends toward center; minimum in alternating ascending order from ends toward center.}}$

This completes the proof.

∎