Nottingham FP Lab Blog

Professor Layton and the Projective Plane

by Christian Sattler on December 7, 2010.
Tagged as: Lunches.

Last Friday, Thorsten came up with a puzzle he encountered while playing “Professor Layton and the Unwound Future” with his son. The statement of the puzzle is as follows:

Puzzle #123 – Cat’s-Eye View:

Goal: Determine the maximum number of stones that can be placed in the [4x4] grid allowing for no four stones to form a square or rectangle horizontally or vertically anywhere on the grid.

He guessed the answer to be 9, though lacking a proof.

The discussion quickly went on to generalizations to arbitrary nxn grids. For the first few n, solutions with 1, 3, 6, 9 stones, respectively, were quickly found. The maximality of these can easily be verified: For example, in the case of a grid size of 4, assume there was a solution with 10 stones. Obviously, no single row can be completely filled with stones, so by the pigeon hole principle, there would have to be two rows with 3 stones each. Again by the pigeon hole principle, these two rows must have stones in at least two common columns, yielding a contradicting rectangle.

Venanzio proposed how to construct, from a valid placement of k stones on an nxn grid, a solution for an (n+1)x(n+1) grid with k+3 stones: Assuming, without loss of generality, that the upper right corner is not inhabited by any stone, add a column to the left and a row to the bottom, placing stones in the three newly created corners. Using this construction, we get solutions with 12, 15, and 18 stones for the 5×5, 6×6, and 7×7 grid, respectively.

But are these solutions maximal in the number of stones? As it turned out, no. There is an intriguing connection of the puzzle to finite projective planes we can use to construct better (and, as it turns out, optimal) solutions. For starters, consider the Fano plane:

The Fano plane is a highly symmetric combinatorial object consisting of 7 points, marked in blue, connected by 7 lines, marked in red. Each point lies on 3 lines and each line connects 3 points. Tabulating the line/point incidence relation in a table, with the rows corresponding to lines and the columns to points, and the numbering as indicated in the above picture, yields the following 7×7 grid:

This gives us a solution with 21 stones, in contrast to the 18 stones predicted above.

This construction generalizes to arbitrary projective planes: In general, a projective plane consists of a set of points and a set of lines, sets of points, such that for every two points, there is exactly one line containing these points, and for every two lines, their intersection consists of exactly one point, together with a certain non-degeneration condition. It can be shown that for finite projective planes, there always exists a natural number n such that the number of points as well as the number of lines is n^2 + n + 1 , every line contains exactly n + 1 points, and every point is contained in exactly n + 1 lines.

Tabulating the line/point incidence relation as we did for the Fano plane, which is in fact the smallest projective plane possible, choosing an arbitrary numbering in the process, we arrive at a placement of (n + 1)(n^2 + n + 1) stones on an $(n^2 + n + 1) \times (n^2 + n + 1)$ grid. This configuration is valid for the following reason: Four stones forming a rectangle in the grid would correspond to two different points being contained in two different lines, violating the uniqueness conditions of the projective plane.

It is worth noting that although identifying lines with rows and points with columns was an arbitrary decision, identifying lines with columns and points with rows does not yield “new” solutions: There is complete symmetry of duality in the definition of projective planes in regard to the notions of points and lines, meaning these two notions can be interchanged without violating the projective plane conditions.

For what values of n is there a projective plane? For any prime power n = p^k , there is a finite field over p^k elements. Over this field, we can build the affine plane with lines the one-dimensional affine subspaces. Taking the projective closure, we have to add an “infinite” intersection point for any class of parallel lines, of which there are p^k + 1 . Finally, we add a line “at infinity” connecting the newly created points. Whether there are projective planes for n not a prime power is an open question.

What remains to be shown is that this construction always yields an optimal solution. For this, consider an arbitrary valid placement of s stones on an mxm grid. For $1 \leq i \leq m$ , let k_i denote the number of stones in the i-th row. Note that $s = \sum_{i=1}^m k_i$ . Each row i gives rise to subsets $\{u, v\}$ of $\{1, \ldots, m\}$ of size 2 having stones in columns u and v. But by the conditions of the puzzle, for any subset $\{u, v\}$ of $\{1, \ldots, m\}$ of size 2, there can be at most one row containing stones in both columns u and v. Since there are only of such size 2 subsets in total, we get the inequality $\sum_{i=1}^m \binom{k_i}{2} \leq \binom{m}{2}$ , or \sum_{i=1}^m k_i (k_i – 1) \leq m (m – 1). Since f(x) := x(x – 1) is a convex function, we can apply Jensen’s inequality:

Multipliying by 4m and adding m^2 , we get 4s(s – m) + m^2 \leq 4m^2(m – 1) + m^2, or (2s – m)^2 \leq m^2(4m – 3), that is, 2s – m \leq m \sqrt{4m – 3}, or

If m is of the form m = n^2 + n + 1 , this simplifies to

which coincides with the number of stones we can place using a projective plane construction, proving it to be optimal.

What is more, we can conversely show that each solution to the puzzle on grid size m for which this bound turns into an equality, which in fact can only happen for m of the form n^2 + n + 1, gives rise to a possibly degenerate projective plane on m points, which is non-degenerate for $n \geq 2$ (the proof is left to the reader). Classes of optimal solutions under row and column renumbering then correspond to isomorphism classes of projective planes. Since on 7 points there is only one projective plane up to isomorphism, we can conclude that our solution for the 7×7 grid is in fact unique (up to row and column renumbering).