TAOCP 5.3.4 Exercise 12
We disprove the statement by providing a counterexample.
Section 5.3.4: Networks for Sorting
Exercise 12. [M20] Prove or disprove: If $x$ and $y$ are bitonic sequences of the same length, so are $x \vee y$ and $x \wedge y$.
Verified: no
Solve time: 1m45s
Solution
We disprove the statement by providing a counterexample.
Let (x = (0, 3, 2, 1)) and (y = (2, 1, 0, 3)). Both sequences have length (4).
Bitonic definition. A sequence is bitonic if it is first monotonically increasing and then monotonically decreasing, or can be circularly shifted to become so. Equivalently, a sequence (\langle z_1,\ldots,z_n\rangle) is bitonic if there exists an index (k) such that [ z_1 \le \cdots \le z_k \ge \cdots \ge z_n \qquad\text{or}\qquad z_1 \ge \cdots \ge z_k \le \cdots \le z_n. ]
Verification that (x) and (y) are bitonic.
- For (x): (0 \le 3 \ge 2 \ge 1). Hence (x) is non‑decreasing up to the second element and non‑increasing thereafter; it is bitonic.
- For (y): (2 \ge 1 \ge 0 \le 3). Hence (y) is non‑increasing up to the third element and non‑decreasing thereafter; it is bitonic.
Compute (x \vee y) and (x \wedge y). The operations (\vee) and (\wedge) denote element‑wise maximum and minimum, respectively. [ \begin{aligned} x \vee y &= (\max(0,2),; \max(3,1),; \max(2,0),; \max(1,3)) = (2, 3, 2, 3),\[2pt] x \wedge y &= (\min(0,2),; \min(3,1),; \min(2,0),; \min(1,3)) = (0, 1, 0, 1). \end{aligned} ]
Neither result is bitonic.
Consider (z = (2,3,2,3)). Its successive differences are (+1,,-1,,+1), so the sequence increases, then decreases, then increases. Any cyclic shift of (z) is either ((2,3,2,3)) or ((3,2,3,2)); both exhibit the pattern up‑down‑up or down‑up‑down, which cannot be made monotonic or single‑peaked by a cyclic shift. Therefore (z) is not bitonic.
Similarly, (w = (0,1,0,1)) has differences (+1,,-1,,+1) and is not bitonic for the same reason.
Thus (x) and (y) are bitonic sequences of the same length, but (x \vee y) and (x \wedge y) are not bitonic. The statement is false. ∎