TAOCP 7.1.3 Exercise 166
Let $X = \operatorname{custer}(X)$, where \operatorname{custer}(X)(i,j)=\overline{X(i,j)} \;\&\; S(i,j), \quad S(i,j)=X(i-1,j)\lor X(i+1,j)\lor X(i,j-1)\lor X(i,j+1).
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 166. [M23] [M23] Let f(M, N) be the maximum number of black pixels in an M × N bitmap X for which X = custer(X). Prove that f(M, N) = 4 5MN + O(M + N).
Verified: no
Solve time: 3m11s
Let $X = \operatorname{custer}(X)$, where
$$ \operatorname{custer}(X)(i,j)=\overline{X(i,j)} ;&; S(i,j), \quad S(i,j)=X(i-1,j)\lor X(i+1,j)\lor X(i,j-1)\lor X(i,j+1). $$
1. Correct analysis of the fixed-point equation
A fixed point must satisfy, for every cell $(i,j)$,
$$ X(i,j)=\overline{X(i,j)} ;&; S(i,j). $$
Let $x = X(i,j)\in{0,1}$ and $s = S(i,j)\in{0,1}$. Then
$$ x = (\neg x)\land s. $$
Case $x=1$
If $x=1$, then
$$ (\neg x)\land s = 0\land s = 0, $$
so the equation becomes $1=0$, impossible. Hence no cell can satisfy $X(i,j)=1$.
Therefore,
$$ X(i,j)=0 \quad \text{for all } (i,j). $$
2. Global consistency condition
Substitute $x=0$ into the fixed-point equation:
$$ 0 = 1 \land s = s. $$
Thus,
$$ S(i,j)=0 \quad \text{for all } (i,j). $$
But $S(i,j)=0$ means all four neighbors of every cell are also $0$. Hence the zero condition propagates across the entire grid, and the configuration
$$ X \equiv 0 $$
is consistent everywhere, including boundaries.
No other configuration is possible.
3. Characterization of all fixed points
The only bitmap satisfying $X=\operatorname{custer}(X)$ is
$$ X(i,j)=0 \quad \text{for all } i,j. $$
Thus the set of black pixels is empty in every fixed point.
4. Value of $f(M,N)$
Since every fixed point has no black pixels,
$$ f(M,N)=0. $$
This holds exactly for all $M,N$, not just asymptotically.
In particular,
$$ f(M,N)=0 = \frac{4}{5}MN + O(M+N) $$
is false as stated in the original claim; the correct value is identically zero.
Conclusion
The fixed-point condition forces every cell to be $0$, hence the only fixed point is the all-zero bitmap and
$$ f(M,N)=0. $$