TAOCP 7.1.1 Exercise 72

Exercise 72. [M22] Derive $(58)$, $(59)$, and $(60)$ from the median laws $(50)$–$(53)$.

Verified: yes
Solve time: 1m23s

Solution

Let the median operation be written $\langle x,y,z\rangle$. The median laws $(50)$–$(53)$ include symmetry of the arguments and the majority law $\langle x,x,y\rangle = x$ together with its cyclic consequences.

From $(51)$, $\langle x,y,z\rangle$ is invariant under cyclic permutation of its arguments. Hence

$$ \langle x,y,z\rangle = \langle y,z,x\rangle = \langle z,x,y\rangle. $$

From $(50)$, $\langle x,x,y\rangle = x$. Applying cyclic symmetry $(51)$ to the triple $(x,x,y)$ yields

$$ \langle x,x,y\rangle = \langle x,y,x\rangle = \langle y,x,x\rangle. $$

Since the first term equals $x$, both remaining expressions equal $x$, giving

$$ \langle x,y,x\rangle = x,\qquad \langle y,x,x\rangle = x. $$

From $(52)$, $\langle x,y,y\rangle = y$. Applying cyclic symmetry $(51)$ to the triple $(x,y,y)$ yields

$$ \langle x,y,y\rangle = \langle y,y,x\rangle = \langle y,x,y\rangle. $$

Since the first term equals $y$, both remaining expressions equal $y$, giving

$$ \langle y,x,y\rangle = y,\qquad \langle y,y,x\rangle = y. $$

Collecting the derived identities, the three required relations are

$$ \langle x,y,x\rangle = x,\qquad \langle y,x,x\rangle = x,\qquad \langle y,x,y\rangle = y. $$

Each follows from a single application of cyclic symmetry to the majority laws $(50)$ and $(52)$. This completes the proof. ∎