This month’s problem is an extension of Question 4 from the 2024 Galois contest. It is not necessary to try the problem before attempting the questions below.
In an \(m\times n\) rectangular grid, we say that two cells are neighbours if they share an edge. The neighbourhood of a cell is the cell itself along with its neighbours.
An \(m\times n\) grid is called a Griffin Grid if each of its \(mn\) cells contains either a \(1\) or a \(-1\) and the integer in every cell is equal to the product of the other integers in its neighbourhood.
For example, the \(4\times 9\) grid below is a Griffin Grid. The three shaded regions are the neighbourhoods of the cells in Row 1 and Column 1, Row 1 and Column 8, and Row 4 and Column 4.
| \(-1\) | \(-1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(-1\) | \(-1\) |
| \(1\) | \(1\) | \(-1\) | \(1\) | \(1\) | \(1\) | \(-1\) | \(1\) | \(1\) |
| \(-1\) | \(1\) | \(-1\) | \(-1\) | \(1\) | \(-1\) | \(-1\) | \(1\) | \(-1\) |
| \(-1\) | \(1\) | \(-1\) | \(1\) | \(1\) | \(1\) | \(-1\) | \(1\) | \(-1\) |
The Galois problem restricted this definition to \(m=3\). Here we want to explore what happens more generally. If a question is marked with an asterisk \((*)\), it means I was unable to solve it. Solutions will not be provided for these problems, but I would love to hear if you solve one!
Show that an \(m\times n\) grid with \(-1\) or \(1\) in every cell is a Griffin Grid if and only if the cells in every neighbourhood have a product of \(1\).
For every \(n\), determine the number of \(2\times n\), \(3\times n\), and \(4\times n\) Griffin Grids. Determining the number of \(3\times n\) Griffin Grids in general is essentially what is required to answer part (c) of the Galois question.
Show that the number of \(m\times n\) Griffin Grids is of the form \(2^k\) for some integer \(k\) with \(0\leq k\leq m\).
\(*\) For general \(m\), determine for which \(k\) there exists \(n\) with the property that the number of \(m\times n\) Griffin Grids is exactly \(2^k\).
Show that for all \(m\) there exist infinitely many \(n\) for which there is exactly one \(m\times n\) Griffin Grid.
Show that for all \(m\) there exist infinitely many \(n\) for which there are \(2^m\) distinct \(m\times n\) Griffin Grids.
* Find a simple general way to calculate the number of \(m\times n\) Griffin Grids.