TAOCP 7.1.3 Exercise 161
We restate the problem in graph-theoretic form.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 161. [20] [20] The cells of a chessboard can be colored black and white, so that neighboring cells have different colors. Does the pentagrid also have this property?
Verified: no
Solve time: 2m10s
We restate the problem in graph-theoretic form.
Let the adjacency graph have one vertex for each cell of the pentagrid, with an edge between two vertices if the corresponding cells share a common boundary segment. The question is whether this graph is bipartite.
Step 1: What must be shown
A cell coloring with two colors so that adjacent cells differ exists if and only if the adjacency graph is bipartite. A graph is bipartite if and only if it admits a 2-coloring of vertices with no edge joining vertices of the same color, equivalently if and only if it contains no odd cycle.
Thus we must determine whether the pentagrid adjacency graph contains any odd cycle.
Step 2: Correct structural model of the pentagrid
The pentagrid arises from five families of parallel lines in the plane, typically indexed by directions $0,1,2,3,4$ cyclically mod 5. These lines partition the plane into convex cells. Each cell is determined by five bounding line segments, one from each family, so that the cell is a convex polygon (often described as a pentagonal region in the construction).
Two cells are adjacent exactly when they share a line segment belonging to one of the five families. Equivalently, moving from a cell to an adjacent cell corresponds to crossing one line of a fixed family index $i \in {0,1,2,3,4}$.
Thus each edge in the adjacency graph is naturally labeled by the index of the line family crossed.
Step 3: Key invariant (parity-type labeling)
Fix an origin cell $C_0$. For any cell $C$, choose a path in the adjacency graph from $C_0$ to $C$. Along this path, record the sequence of crossed line families $i_1,i_2,\dots,i_k$.
Define a label
$$ \phi(C) = \sum_{j=1}^k i_j \pmod 2. $$
We must show this is well-defined, i.e., independent of the chosen path. This holds because any closed loop in the adjacency graph corresponds to moving across lines and returning to the original region. Along such a loop, for each family $i$, the number of crossings of lines of type $i$ is even: every crossing from one side of a line is paired with a return crossing back across a parallel translate of that same family. Hence each $i_j$ contributes an even total number of times modulo 2, so the total sum is $0 \pmod 2$. Therefore $\phi$ is well-defined.
Thus every cell is assigned a parity value in ${0,1}$.
Step 4: Adjacency flips parity
If two cells $C$ and $C'$ are adjacent, they differ by crossing exactly one line, say of family $i$. Any path to $C'$ is obtained from a path to $C$ by appending one additional crossing labeled $i$. Therefore
$$ \phi(C') = \phi(C) + i \pmod 2, $$
so in particular $\phi(C') \neq \phi(C)$ since $i \in {0,1,2,3,4}$ and contributes a nonzero change mod 2.
Hence adjacent cells always receive different values of $\phi$.
Step 5: Construction of a 2-coloring
Color each cell black if $\phi(C)=0$ and white if $\phi(C)=1$. By the previous step, adjacent cells have opposite colors.
Thus the adjacency graph is bipartite.
Step 6: Conclusion
A consistent 2-coloring exists for the pentagrid cell adjacency graph. Therefore the pentagrid has the same 2-colorability property as the chessboard.
$$ \boxed{\text{Yes, the pentagrid is 2-colorable.}} $$