TAOCP 7.1.1 Exercise 59
The flaw in the previous solution is exactly that it tries to match _pairs indexed by the same $Q'$_ with _pairs indexed by the same $a'$_ using only multiset equalities.
Exercise 59. [M20] [M20] (D. Pehoushek and R. Frier, 1997.) If the truth table for $f(x_1, x_2, \ldots, x_n)$ has a 1 in exactly $k$ places, show that exactly $k$ of the fully quantified formulas $Q_1 x_1 ; Q_2 x_2, Q_n x_n, f(x_1, x_2, \ldots, x_n)$ are true when each $Q_i$ is either $\exists$ or $\forall$.
Verified: no
Solve time: 5m55s
The flaw in the previous solution is exactly that it tries to match pairs indexed by the same $Q'$ with pairs indexed by the same $a'$ using only multiset equalities. That is invalid, because multisets carry no canonical pairing information.
A correct proof avoids any such pairing and instead tracks how quantifier evaluation acts on the truth table as a structure-preserving transformation that preserves the number of ones at every step.
Correct solution
Let $f:{0,1}^n \to {0,1}$ have exactly $k$ ones in its truth table. We prove that among all fully quantified formulas
$$ Q_1 x_1, Q_2 x_2 \cdots Q_n x_n, f(x_1,\dots,x_n), \quad Q_i \in {\exists,\forall}, $$
exactly $k$ evaluate to $1$.
Step 1: View evaluation as iterative elimination
Fix a prefix $Q_1 x_1 \cdots Q_n x_n$. Evaluate the formula by eliminating variables from right to left.
Given a Boolean function $g(x_1,\dots,x_n)$, define:
$$ (\exists x_n, g)(x_1,\dots,x_{n-1}) = g_0 \lor g_1, \quad (\forall x_n, g)(x_1,\dots,x_{n-1}) = g_0 \land g_1, $$
where
$$ g_0 = g(x_1,\dots,x_{n-1},0), \quad g_1 = g(x_1,\dots,x_{n-1},1). $$
Thus each quantifier replaces every pair of leaf values $(g_0, g_1)$ by either:
$$ (g_0 \lor g_1) \quad \text{or} \quad (g_0 \land g_1). $$
Step 2: Key invariant on pairs
For any pair $(A,B) \in {0,1}^2$,
$$ {A \lor B,; A \land B} = {A,B} \quad \text{as multisets.} $$
Hence, each quantifier step replaces each pair of values by another pair with the same multiset.
Step 3: Inductive invariant (correct form)
Define $S(f)$ as the multiset of values obtained by evaluating all $2^n$ fully quantified formulas built from $f$.
We prove:
$S(f)$ is invariant under one quantifier elimination step in the sense that eliminating a variable preserves the multiset of truth-table values.
More precisely, after eliminating $x_n$, the collection of resulting values over all quantifier choices corresponds to replacing each pair $(f_0(a'), f_1(a'))$ by either $\lor$ or $\land$, but across all choices both outcomes appear exactly once per pair, hence the multiset of resulting values is unchanged.
Step 4: Crucial counting argument (no pairing)
Fix $f_0(a') = f(a',0)$ and $f_1(a') = f(a',1)$. For each fixed $a'$, consider the two possible outcomes:
$$ f_0(a') \lor f_1(a'), \quad f_0(a') \land f_1(a'). $$
Across all choices of the last quantifier, each of these two values appears exactly once for that $a'$.
Thus, for each fixed $a'$, the contribution of the pair $(f(a',0), f(a',1))$ to the global multiset is exactly:
$$ {f(a',0), f(a',1)}. $$
Summing over all $a'$, the multiset of all outcomes after quantifying $x_n$ is exactly the multiset of all original truth-table values of $f$, merely regrouped.
Importantly, this argument does not require pairing outputs across different $Q'$.
Step 5: Iterating the argument
Apply the same reasoning inductively for $x_{n-1}, x_{n-2}, \dots, x_1$.
At each step:
- values are grouped into disjoint pairs,
- each pair $(A,B)$ is replaced by two outputs whose multiset is exactly ${A,B}$,
- therefore the global multiset of values is invariant.
Thus after all $n$ eliminations, the multiset of values of all fully quantified formulas equals the original truth-table multiset:
$$ S(f) = { f(a) : a \in {0,1}^n }. $$
Step 6: Final counting
Since $f$ has exactly $k$ ones in its truth table, the multiset on the right contains exactly $k$ ones.
Therefore the multiset $S(f)$, which is precisely the collection of truth values of all fully quantified formulas, also contains exactly $k$ ones.
Hence exactly $k$ of the $2^n$ quantified formulas evaluate to $1$.
Conclusion
$$ \boxed{\text{Exactly } k \text{ of the fully quantified formulas are true.}} $$
The correction eliminates the invalid step in the original proof by removing any assumed correspondence between different indexings and replacing it with a purely local invariant: each quantifier step preserves the multiset of values pairwise, hence globally.