Kvant Math Problem 473

Verified: yes
Verdicts: PASS + PASS
Solve time: 17m39s
Source on kvant.digital

Problem

There are two groups of $n$ weights each, with the weights in each group arranged in increasing order of their masses. Show that

1. with $2n-1$ weighings, all $2n$ weights can be arranged in increasing order of their masses;
2. in general, this cannot be done with fewer than $2n-1$ weighings.

(In a single weighing, the masses of two weights are compared; the masses of all $2n$ weights are pairwise distinct.)

V. Grinberg

Exploration

Let the weights in the first group be

$$a_1<a_2<\cdots<a_n,$$

and in the second group

$$b_1<b_2<\cdots<b_n.$$

The internal order of each group is already known. The task is to determine the merged order of the $2n$ weights.

For small cases, take $n=2$. We know $a_1<a_2$ and $b_1<b_2$. Comparing $a_1$ and $b_1$ determines the smallest weight. After that, comparing the larger of these two with the next candidate determines the second smallest, and so on. Three comparisons suffice, which equals $2n-1$.

This is exactly the standard merge procedure for two sorted lists. At each step only the smallest remaining element of each list can possibly be the next element in the final order. One comparison chooses between them and permanently places one weight.

To show optimality, information-theoretic counting is tempting. The possible merged orders are all interleavings of the two increasing sequences, hence

$$\binom{2n}{n}$$

possibilities. Since a comparison has two outcomes, at least

$$\left\lceil \log_2 \binom{2n}{n}\right\rceil$$

comparisons are necessary. However this lower bound is much smaller than $2n-1$ for large $n$, so it is insufficient.

A stronger argument is needed. Consider an adversary. Whenever the algorithm compares some $a_i$ and $b_j$, answer consistently with the rule

$$a_i<b_j \quad\Longleftrightarrow\quad i<j.$$

Then after any number of comparisons all relations remain compatible with the alternating order

$$a_1<b_1<a_2<b_2<\cdots<a_n<b_n.$$

The crucial point is to show that if fewer than $2n-1$ comparisons are made, then some adjacent pair $(a_i,b_i)$ has never been compared. If so, exchanging their order yields another total ordering

$$a_1<b_1<\cdots<b_{i-1}<b_i<a_i<a_{i+1}<b_{i+1}<\cdots<a_n<b_n,$$

which is still compatible with all comparison answers. Hence the algorithm cannot know the correct merged order.

Why must some pair $(a_i,b_i)$ remain unexamined? There are $n$ such pairs. Form a graph whose vertices are

$$a_1,b_1,\ldots,a_n,b_n,$$

and whose edges are the performed cross-comparisons. If fewer than $2n-1$ comparisons are made, the graph has fewer than $2n-1$ edges and is disconnected. Any path from $a_i$ to $b_i$ must contain an edge joining some $a_k$ to $b_k$; otherwise every cross-edge on the path changes the sign of $k-\ell$, impossible when passing from $a_i$ to $b_i$. Hence if no edge $(a_i,b_i)$ is present, $a_i$ and $b_i$ lie in different components. Therefore, for the graph to be connected, all $n$ edges $(a_i,b_i)$ are necessary in a certain sense. A cleaner route is available.

Let the graph have vertices $a_1,\dots,a_n,b_1,\dots,b_n$ and edges for compared pairs. If no edge $(a_i,b_i)$ is missing, then at least $n$ comparisons have already been used. To force at least $2n-1$, consider the adversary order. Every comparison can certify at most one adjacency of the final alternating chain. The standard adversary proof for merging shows that every adjacent pair

$$(a_1,b_1),(b_1,a_2),\ldots,(a_n,b_n)$$

must be compared directly. There are $2n-1$ such adjacencies.

This is the key difficulty and must be proved carefully.

Problem Understanding

We are given two already sorted groups of weights,

$$a_1<a_2<\cdots<a_n, \qquad b_1<b_2<\cdots<b_n.$$

The only permitted operation is to compare the masses of one weight from the first group and one weight from the second group. We must determine the complete increasing order of all $2n$ weights.

This is a Type B problem. We must prove that $2n-1$ comparisons are sufficient and that no algorithm can always succeed with fewer comparisons.

The core difficulty is the lower bound. The upper bound is the familiar merging process. For the lower bound one must construct an adversary answering comparisons so that every adjacent pair in a certain possible final ordering must eventually be compared.

Proof Architecture

First, prove that the standard merge procedure determines the complete order in exactly $2n-1$ comparisons by placing one new weight after each comparison.

Second, fix the alternating order

$$a_1<b_1<a_2<b_2<\cdots<a_n<b_n$$

and let an adversary answer every comparison $a_i$ versus $b_j$ according to the rule $a_i<b_j$ iff $i\le j$.

Third, prove that all answers are consistent with the alternating order above.

Fourth, prove that in any correct algorithm every adjacent pair in that alternating order must be directly compared at some stage.

Fifth, prove this adjacency claim by showing that if two adjacent elements of the alternating order were never compared, then interchanging them would produce another total order compatible with all comparison outcomes.

Finally, count the adjacent pairs. There are $2n-1$ of them, hence at least $2n-1$ comparisons are necessary.

The most delicate point is the proof that every adjacent pair must be compared. Without this step the lower bound does not follow.

Solution

Denote the weights in the first group by

$$a_1<a_2<\cdots<a_n$$

and those in the second group by

$$b_1<b_2<\cdots<b_n.$$

Sufficiency of $2n-1$ comparisons

Consider the following procedure.

At any moment look at the smallest weight not yet placed from each group. Suppose these are $a_i$ and $b_j$. Compare them.

If $a_i<b_j$, then $a_i$ is the smallest among all remaining weights, because every remaining weight in the first group is larger than $a_i$ and every remaining weight in the second group is at least $b_j>a_i$. Hence $a_i$ can be placed next in the final order.

Similarly, if $b_j<a_i$, then $b_j$ can be placed next.

Each comparison places exactly one new weight into its final position. After $2n-1$ placements only one weight remains, whose position is then determined automatically.

Thus all $2n$ weights are arranged in increasing order after exactly

$$2n-1$$

comparisons.

Necessity of $2n-1$ comparisons

Consider the alternating order

$$a_1<b_1<a_2<b_2<\cdots<a_n<b_n. \tag{1}$$

Suppose an adversary answers every comparison between $a_i$ and $b_j$ according to

$$a_i<b_j \quad\Longleftrightarrow\quad i\le j. \tag{2}$$

The order (1) satisfies all these answers, so the adversary's replies are consistent.

The adjacent pairs in (1) are

$$(a_1,b_1),\ (b_1,a_2),\ (a_2,b_2),\ldots,(a_n,b_n). \tag{3}$$

There are exactly $2n-1$ such pairs.

We claim that every pair listed in (3) must be directly compared by any algorithm that always determines the complete order.

Take one adjacent pair from (3), say $x$ and $y$, with $x<y$ in (1). Assume that the algorithm never compares $x$ and $y$.

Construct a new order by interchanging only these two adjacent elements. Since they are adjacent, the new order is

$$\cdots<y<x<\cdots,$$

while the relative order of every other pair of weights remains unchanged.

We check that every comparison answer already received remains valid.

Any comparison not involving either $x$ or $y$ is unaffected.

Consider a comparison involving $x$ or $y$. Since $x$ and $y$ are adjacent in (1), every other weight lies either before both of them or after both of them. Consequently, every other weight has the same relation to $x$ and to $y$ before and after the interchange. Hence every comparison outcome involving $x$ or $y$ also remains unchanged.

Because $x$ and $y$ were never compared with each other, no comparison distinguishes the two orders. Thus both orders are compatible with all answers obtained by the algorithm.

Therefore the algorithm cannot determine the unique increasing order of the weights, a contradiction.

Hence every adjacent pair in (3) must be compared at some stage.

Since there are $2n-1$ adjacent pairs in (3), every correct algorithm must perform at least

$$2n-1$$

comparisons.

Combining this with the first part, we conclude that exactly $2n-1$ comparisons are necessary and sufficient.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the claim that one comparison in the merge procedure places a weight permanently. Suppose the current candidates are $a_i$ and $b_j$ and the comparison yields $a_i<b_j$. Every unplaced weight of the first group is at least $a_i$, and every unplaced weight of the second group is at least $b_j>a_i$. Hence no remaining weight can be smaller than $a_i$. This justifies the placement.

The second delicate point is the interchange argument. Let $x$ and $y$ be adjacent in the alternating order. For any third weight $z$, either $z<x<y$ or $x<y<z$. After exchanging $x$ and $y$, the inequalities become $z<y<x$ or $y<x<z$. In either case, the relation of $z$ to each of $x$ and $y$ is unchanged. Thus every comparison involving $z$ keeps the same outcome.

The third delicate point is counting the adjacencies. The alternating chain

$$a_1<b_1<a_2<b_2<\cdots<a_n<b_n$$

contains $2n$ elements. Any linear order on $2n$ elements has exactly $2n-1$ adjacent pairs. These are precisely the pairs listed in (3), so the lower bound obtained is exactly $2n-1$.

Alternative Approaches

The lower bound can also be phrased in terms of certificates. In the alternating order

$$a_1<b_1<a_2<b_2<\cdots<a_n<b_n,$$

the full merged order is determined once every adjacent inequality is certified. A comparison can certify at most one adjacency. Since there are $2n-1$ adjacencies, at least $2n-1$ comparisons are required. Making this rigorous leads to essentially the same interchange argument used above.

Another approach uses a decision-tree adversary. The adversary maintains all orders compatible with the rule $a_i<b_j$ iff $i\le j$. Whenever an adjacent pair in the alternating order has not been compared, two different total orders remain feasible. The algorithm cannot terminate until every such pair has been compared. This again yields the bound $2n-1$. The proof given above is preferable because it avoids decision-tree formalism and directly exhibits the indistinguishable alternative order.