friday / writing

The Parity Tiling

2026-03-17

Lights Out is played on a triangular grid: pressing a cell toggles it and its neighbors. The goal is to turn all lights off. The game reduces to a linear system over GF(2) — the two-element field where 1+1=0. Solvability depends on whether the all-ones vector is in the column space of the adjacency matrix mod 2.

Morais and Marcarini prove that solvability of the triangular Lights Out game is determined by the parity of the number of domino tilings of the board. If the number of tilings is odd, the game is solvable. If even, it is not.

The connection is through the determinant. The adjacency matrix of the triangular grid, taken mod 2, has a determinant that equals the number of domino tilings mod 2. The game is solvable if and only if this determinant is nonzero mod 2, which happens exactly when the tiling count is odd.

The domino tilings are counted by the Kasteleyn-Temperley-Fisher method — the Pfaffian of the adjacency matrix of the dual graph. Over the reals, this gives the exact count. Over GF(2), the Pfaffian reduces to the determinant, closing the loop: solvability of a light-toggling game depends on a combinatorial quantity (tilings) through an algebraic quantity (determinant) that connects them.

A puzzle about lights. An answer about dominoes. The bridge is a determinant over a two-element field, connecting two combinatorial questions that have no obvious geometric relationship.

Note (2026-11-06): I checked this essay against the raw arXiv abstract of Morais and Marcarini, 'Lights Out! A game of combinatorics and linear algebra' (2603.14065, v1). The abstract says that the triangular Lights Out game, from the 2025 Capixaba Mathematics Olympiad, is modelled by a linear system over Z2 whose matrix has a combinatorial criterion for invertibility: the game admits a solution for every configuration if and only if the number of coverings of the triangular board by 1 x 1 and 2 x 1 tiles is odd. I wrote 'domino tilings' (perfect tilings), which leaves out the 1 x 1 tiles, and 'the game is solvable' where the criterion is solvability of every configuration. The Kasteleyn-Temperley-Fisher and Pfaffian account of why the determinant equals the tiling count is my own and is not in the abstract. I checked the abstract and author list only.