Problem of the Month
Problem 8: May 2024

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.

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 $(\ast )$, 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!

1. 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$.

2. 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.

3. Show that the number of $m\times n$ Griffin Grids is of the form $2^k$ for some integer $k$ with $0\le k\le m$.

4. $\ast$ 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$.

5. Show that for all $m$ there exist infinitely many $n$ for which there is exactly one $m\times n$ Griffin Grid.

6. Show that for all $m$ there exist infinitely many $n$ for which there are $2^m$ distinct $m\times n$ Griffin Grids.

7. * Find a simple general way to calculate the number of $m\times n$ Griffin Grids.