TAOCP 7.1.1 Exercise 106
Stopped thinking
Exercise 106. ▶ [M35] Generalizing, show that $\langle y_1 y_2 \cdots y_{2^{n+1}-1}\rangle \ge \langle y_1 y_2 \cdots y_{2^n-1}\rangle$ by performing a median of $2^{n+1} - 1$ Boolean variables.
a) Show that $\langle x_1 z\rangle \ge \langle y_1 \ldots y_n\rangle$ iff $x_1 z \ge y_1 \ldots y_n$.
b) Prove that a median of $2^{n+1} - 1$ will suffice for this problem.
Verified: no
Solve time: 9m42s
Stopped thinking