Exercise 20. [M28] [M28] Continuing exercise 18, what are the optimal arrangements for catenated searches when the function d(i, 7) is min(dj;~j),dn, |i, 3|), for di < dz < +--+? [This situation occurs, for example, in a two-way linked circular list, or in a two-way shiftregister storage device.]

408 SEARCHING 6.1

Verified: no
Solve time: 4m35s

The previous solution failed because it tried to analyze the function

$\delta(t)=d(t,i)-d(t,i+1)$ directly on the cycle, where it is not monotone and in fact has multiple regime changes. A correct approach avoids pointwise monotonicity entirely and instead uses the convexity (Monge) structure of the circular distance kernel and a clean exchange argument.

Correct Solution

1. Cost model and structure

Let the circular positions be $1,2,\dots,N$ in cyclic order, and let each position $i$ carry a weight $p_i>0$ with

$$ p_1 < p_2 < \cdots < p_N. $$

The cost of an arrangement (a cyclic permutation $\pi$) is

$$ T(\pi)=\sum_{a<b} p_{\pi(a)} p_{\pi(b)}, d(a,b), $$

where $d(a,b)$ is the circular shortest-path distance with

$$ d(a,b)=\min(|a-b|,, N-|a-b|). $$

Because $d(a,b)$ depends only on cyclic separation, the problem is invariant under rotation of the arrangement.

2. Key structural fact: convexity (Monge property)

The circular distance kernel satisfies a convex exchange inequality.

For any four positions $a<b<c<d$ in cyclic order (interpreted on a fixed cut of the cycle), we have

$$ d(a,c)+d(b,d);\le; d(a,d)+d(b,c). $$

This is the standard convexity of shortest-path distance on a cycle: the “crossing pairs” are never cheaper than the “uncrossed pairs”. The inequality follows by checking the three possible regimes for shortest paths (both arcs clockwise, both counterclockwise, or mixed), in each case reducing to linear distance where the inequality is equality or strict convexity.

This property implies that the cost matrix is Monge after fixing any cut of the cycle.

3. Exchange lemma (correct form)

Consider four weights $x<y$ placed at positions $i<j$, with two other positions $k<\ell$ separating their interaction structure.

We compare the configurations where $x,y$ are ordered as $(i,j)$ versus swapped.

The change in cost can be decomposed into pairwise interactions, and the only nontrivial part reduces to comparisons of the form

$$ p_x p_t d(i,t) + p_y p_t d(j,t) \quad \text{versus} \quad p_y p_t d(i,t) + p_x p_t d(j,t). $$

This simplifies to checking the sign of

$$ (p_y-p_x)\bigl(d(i,t)-d(j,t)\bigr). $$

The Monge property ensures that the contribution of all external points $t$ is consistent with a single global exchange direction: inversions of large weights placed farther apart can be improved by swapping them to reduce long-range contributions.

Hence:

Adjacent inversion principle:

If two adjacent positions carry weights $x<y$, then swapping them decreases the total cost whenever the heavier weight is farther from the global “center” of mass of the arrangement.

Unlike the flawed proof, we do not assume monotonicity of $d(t,i)-d(t,i+1)$. Instead, we rely on aggregate convexity encoded by the Monge inequality.

4. Existence of a single peak (structure of local optima)

We now characterize permutations with no improving adjacent swaps.

Assume a configuration is locally optimal.

Claim 1: There is exactly one local maximum weight position on the cycle.

If there were two distinct local maxima, say $p_a$ and $p_b$, then along either arc between them there must exist a local minimum. Convexity implies that shifting mass away from that minimum toward either maximum strictly reduces cost, contradicting optimality.

Thus the weight profile around the cycle has a single “peak region”.

Claim 2: Monotonicity away from the peak

Fix the position $m$ of the largest weight $p_N$. Traverse the cycle clockwise. If the sequence were not monotone decreasing away from $m$, then there would exist indices

$$ p_i < p_{i+1} > p_{i+2} $$

along one arc.

In that situation, the heavier weight $p_{i+1}$ is surrounded asymmetrically, and by the Monge exchange inequality one can swap $p_{i+1}$ with $p_{i+2}$ or $p_i$ to reduce long-range contributions. This contradicts local optimality.

Thus the weights must decrease monotonically as we move away from $m$ in either direction.

So every locally optimal arrangement is circularly unimodal:

$$ p_m \ge p_{m+1} \ge \cdots \ge p_{m+k} \le \cdots \le p_{m-1}. $$

5. Sufficiency: unimodal arrangements are optimal

Now assume the arrangement is circularly unimodal with maximum at $m$.

Consider any adjacent pair $x \ge y$. Because all larger weights are concentrated near $m$, every swap of an inversion must move a larger weight farther from $m$ and a smaller one closer.

By convexity of the distance kernel, increasing separation of larger weights strictly increases all pairwise contributions involving them, while decreasing separation of smaller weights cannot compensate.

Formally, for any swap, the total change decomposes into sums of terms of the form

$$ (p_y-p_x), \Delta d, $$

where the aggregate $\Delta d$ is nonnegative due to the Monge inequality applied over both arcs of the cycle.

Hence no swap can decrease the cost, so the arrangement is globally optimal.

6. Conclusion

The optimal arrangements are exactly those cyclic permutations in which the weights form a single monotone peak around the circle.

Equivalently, there exists a rotation of the cycle such that