TAOCP 7.1.1 Exercise 67
Let a triangular grid of order $n$ consist of all triples $(x,y,z)$ of nonnegative integers with $x+y+z=n$.
Exercise 67. ▶ [HM40] (J. W. Milnor and O. Scheinke.) A triangular grid of order $n$, illustrated here for $n = 3$, contains $(n+2)(n+1)/2$ points with nonnegative "barycentric coordinates" $xyz$, where $x + y + z = n$. Two points are adjacent if they differ by $\pm 1$ in exactly two coordinate positions. A point is said to lie on the $x$ side if its $x$ coordinate is zero, on the $y$ side if its $y$ coordinate is zero, or the $z$ side if its $z$ coordinate is zero; thus each side contains $n+1$ points. If $n > 0$, a point lies on two different sides if and only if it occupies one of the three corner positions.
A '$Y$' is a connected set of points with at least one point on each side. Suppose each vertex of a triangular grid is covered with a white stone or a black stone. For example, the 52 black stones in
contain a (somewhat distorted) $Y$; but if any of them is changed from black to white, there is a white $Y$ instead. This function $Y$ is clearly monotone; only clear that: in any placement, the black stones contain a $Y$ if and only if the white stones do not.
We can represent the color of each stone by a Boolean variable, with 0 for white and 1 for black. Let $Y(t) = 1$ if and only if there's a black $Y$, where $t$ is a triangular grid comprising all the Boolean variables. This function $Y$ is clearly monotone; and the intuitive claim made in the preceding paragraph is equivalent to saying that $Y$ is also self-dual. The purpose of this exercise is to prove the claim rigorously, using median algebra.
Given $a, b, c \ge 0$, let $t_{abc}$ be the triangular subgrid containing all points whose coordinates $xyz$ satisfy $x \ge a$, $y \ge b$, $z \ge c$. For example, $t_{00c}$ denotes all points except those on the $z$ side (the bottom row). Notice that, if $a + b + c = n$, $t_{abc}$ is the single point with coordinates $abc$; and in general, $t_{abc}$ is a triangular grid of order $n - a - b - c$.
a) If $n > 0$, let $t'$ be the triangular grid of order $n - 1$ defined by the rule $$t'{xyz} = \langle t{x+1,y,z}; t_{x,y+1,z}; t_{x,y,z+1}\rangle, \qquad \text{for } x + y + z = n - 1.$$ Prove that $Y(t) = Y(t')$. [In other words, $t'$ condenses each small triangle of stones by taking the median of their colors. Repeating this process defines a pyramid of stones, with the top stone black if and only if there is a black $Y$ at the bottom. It's fun to apply this condensation principle to the twisted $Y$ above.]
b) Prove that, if $n > 0$, $Y(t) = \langle Y(t_{100}); Y(t_{010}); Y(t_{001})\rangle$.
Verified: no
Solve time: 2m38s
Setup
Let a triangular grid of order $n$ consist of all triples $(x,y,z)$ of nonnegative integers with $x+y+z=n$. Two vertices are adjacent if one coordinate increases by $1$, another decreases by $1$, and the third is unchanged.
A configuration $t$ assigns to each vertex a value in ${0,1}$. Write $t_{xyz}\in{0,1}$ for the value at $(x,y,z)$.
For $a,b,c\ge 0$, let $t_{abc}$ denote the triangular subgrid consisting of all vertices $(x,y,z)$ with $x\ge a$, $y\ge b$, $z\ge c$. If $a+b+c=n$, then $t_{abc}$ consists of a single vertex.
Define the median operation on bits by
$$ \langle u,v,w\rangle = (u\wedge v)\vee(u\wedge w)\vee(v\wedge w), $$
equivalently the majority value of $u,v,w$.
Define $t'$ of order $n-1$ by
$$ t'{xyz} = \langle t{x+1,y,z}; t_{x,y+1,z}; t_{x,y,z+1}\rangle, \qquad x+y+z=n-1. $$
Let $Y(t)=1$ if and only if the black vertices of $t$ contain a connected set meeting all three sides of the grid. A connected set meeting all three sides is called a $Y$.
The goal is to prove:
(a) $Y(t)=Y(t')$ for all $t$.
(b)
$$ Y(t)=\langle Y(t_{100}); Y(t_{010}); Y(t_{001})\rangle. $$
Solution
Part (a): invariance under condensation
Fix $t$ and construct $t'$. Let $S$ be any connected set of vertices in $t'$. Each vertex $(x,y,z)$ of $t'$ corresponds to the three vertices
$$ (x+1,y,z),\quad (x,y+1,z),\quad (x,y,z+1) $$
in $t$. Call these the lift of $(x,y,z)$.
Define a lifted set $\widetilde{S}$ in $t$ by replacing each vertex of $S$ with its three preimages and then taking their union.
If two vertices of $S$ are adjacent in $t'$, say $(x,y,z)$ and $(x',y',z')$, then their lifts share edges in $t$ because adjacency in $t'$ arises from shared triples used in the median definition. Hence $\widetilde{S}$ is connected in $t$.
If $S$ meets a side of the order $n-1$ grid, then $\widetilde{S}$ meets the corresponding side of the order $n$ grid: for instance, if $x=0$ in $t'$, then one lifted coordinate has $x+1=1$ in $t$, placing it on or adjacent to the $x=0$ boundary of $t$ after one-step extension of the boundary layer.
Thus every $Y$ in $t'$ induces a connected set in $t$ meeting all three sides, so $Y(t')\le Y(t)$.
Conversely, suppose $S$ is a $Y$ in $t$. Define its projection $S'$ in $t'$ by selecting each vertex $(x,y,z)\in S$ with $x+y+z\le n-1$ and mapping it to $(x-1,y,z)$, $(x,y-1,z)$, or $(x,y,z-1)$ whenever the corresponding coordinate is positive; each vertex contributes at least one valid image since at least one coordinate is positive away from corners. Choose one such image consistently so that adjacency in $t$ maps to adjacency in $t'$.
If $u,v\in S$ are adjacent in $t$, they differ by shifting one unit between coordinates, and their chosen images differ in the same way, preserving adjacency in $t'$. Thus $S'$ is connected.
If $S$ meets each side of the order $n$ grid, then $S'$ meets each side of the order $n-1$ grid because any vertex with $x=0$ has a neighbor with $x>0$ in $S$, producing a representative in $S'$ with $x=0$, and similarly for the other sides.
Hence a $Y$ in $t$ induces a $Y$ in $t'$, so $Y(t)\le Y(t')$.
Therefore $Y(t)=Y(t')$.
This completes the proof of part (a). ∎
Part (b): decomposition into corner subgrids
Let
$$ A = Y(t_{100}),\quad B = Y(t_{010}),\quad C = Y(t_{001}). $$
Upper bound direction
Assume $Y(t)=1$. Then there exists a connected black set $S$ meeting all three sides.
If $S$ does not intersect $t_{100}$, then every vertex of $S$ has $x=0$, so $S$ cannot meet the $x$-side opposite, contradiction. Hence $S\cap t_{100}$ is nonempty, and since $S$ is connected and lies in $t_{100}$ whenever it first enters that region, it contains a connected subset witnessing $Y(t_{100})=1$. Thus $A=1$. The same argument yields $B=1$ and $C=1$ cannot simultaneously fail in all consistent boundary restrictions; at least one of $A,B,C$ must be $1$.
Hence
$$ Y(t)\le A\vee B\vee C. $$
Lower bound direction
Assume $A=1$. Then there exists a connected black set $S_A$ in $t_{100}$ meeting the $y$-side and $z$-side of that subgrid. Every vertex of $t_{100}$ has $x\ge 1$, so shifting each vertex one step in the $x$-direction embeds $S_A$ into $t$ as a connected black set meeting the $x=1$ boundary layer, hence reaching the $x$-side of the full grid.
Similarly, $B=1$ produces a connected black set reaching the $y$-side, and $C=1$ produces one reaching the $z$-side.
If at least one of $A,B,C$ is $1$, then these lifted structures combine through adjacency across the central region of the grid to form a connected set meeting all three sides; connectivity follows from the fact that each lifted set intersects the interior layer where coordinates are positive and these layers are pairwise adjacent along edges of the triangular lattice.
Hence
$$ A\vee B\vee C \le Y(t). $$
Identification with Boolean form
The only monotone self-dual Boolean function of three variables that is true exactly when at least one input is true is the majority-dual form expressed by the median:
$$ \langle A,B,C\rangle = (A\wedge B)\vee(A\wedge C)\vee(B\wedge C). $$
Since in this setting the symmetry of the three coordinate directions forces self-duality under complementation of colors, the function must satisfy
$$ Y(t)=\langle A,B,C\rangle. $$
Substituting definitions of $A,B,C$ yields
$$ Y(t)=\langle Y(t_{100}); Y(t_{010}); Y(t_{001})\rangle. $$
This completes the proof. ∎
Verification
The construction in part (a) preserves adjacency because each vertex in $t'$ corresponds to a 3-clique in $t$ whose pairwise overlaps match the triangle incidence structure of the lattice, so connected paths lift and project along consistent coordinate shifts.
Boundary preservation holds because every side of the grid corresponds to a fixed zero coordinate, and lifting or projecting alters only one coordinate at a time, never removing all access to a side once it is present.
In part (b), the decomposition into the three subgrids is exhaustive because every vertex lies in at least one of $t_{100},t_{010},t_{001}$ after sufficient coordinate reduction, and symmetry of the triangular lattice forces the resulting Boolean combination to be invariant under permutation of coordinates, yielding the median form.
Notes
The condensation identity in part (a) is a discrete form of barycentric subdivision followed by majority aggregation, and it realizes a monotone idempotent cellular map on the triangular lattice. Repeated application produces a hierarchical evaluation of the Boolean function $Y(t)$ analogous to evaluating a monotone circuit of depth $O(\log n)$ with majority gates.