Suppose an \(m\times n\) grid with a \(1\) or \(-1\) in every cell is a Griffin Grid. Consider an arbitrary cell \(C\) and suppose it contains the integer \(a\) (so \(a=1\) or \(a=-1\)). Let \(b\) be the product of the integers in the neighbours of \(C\). Since the grid is a Griffin Grid, we have \(a=b\). The product of the integers in the neighbourhood of \(C\) is \(ab=a^2=1\), since \(1^2=(-1)^2=1\).
Now suppose an \(m\times n\) grid has a \(1\) or a \(-1\) in every cell and that the product of the integers in every neighbourhood is \(1\). Let \(C\) be an arbitrary cell, let \(a\) be the integer in \(C\), and let \(b\) be the product of the integers in the neighbours of \(C\). To verify that the grid is a Griffin Grid, we need to show that \(a=b\).
We are assuming that \(ab=1\), and we know that \(a=\pm1\) and \(b=\pm 1\) because it is the product of some integers, all of which are either \(1\) or \(-1\). If \(a\) and \(b\) were different, then their product would be \(-1\), not \(1\). Therefore, \(a=b\).
Using similar reasoning to that which was used in part (a), it can be shown that an \(m\times n\) grid with \(1\) or \(-1\) in every cell is a Griffin Grid if and only if for every neighbourhood in the grid, the integer in each cell in the neighbourhood is equal to the product of the other cells in that neighbourhood.
In any \(2\times n\) grid with \(1\) or \(-1\) in every cell, there are only four possibilities for the first column. They are shown below.
As suggested in the hint, we will now try to understand Griffin Grids with \(2\) rows and infinitely many columns. We will refer to such a grid as a \(2\times \infty\) Griffin Grid.
The second column can be completely determined from the first column using the observation at the beginning of this part of the solution. Specifically, consider the two neighbourhoods highlighted below:
In both of these three-cell neighbourhoods, the integer in the second column is equal to the product of the integers in the first column. Thus, for each of the four possible first columns, we can compute the second column as follows:
From here, we can see that there is exactly one \(2\times 2\) Griffin Grid. This is because there are only four possible ways to fill in the first column, and if a \(2\times 2\) grid is to be a Griffin Grid, then its second column must be filled in according to the appropriate grid above. If we imagine "chopping off" the first two columns of the infinite grids above, only the first of the four \(2\times 2\) grids gives a Griffin Grid.
Continuing in this way, we can examine \(2\times 3\) Griffin Grids by filling in the next column. This can be done using the neighbourhoods shown below.
Similar to before, the integers in these neighbourhoods that are in the third column are equal to the product of the integers (in the respective neighbourhood) in the first two columns. Thus, if the cells in the first two columns contain the integers \(a\), \(b\), \(c\), and \(d\), as shown, then the cells in the third column are as shown.
However, we can simplify this a little bit. From earlier, we know that \(c=d=ab\). As well, \(a^2=b^2=c^2=d^2=1\) since each of the variables \(a\), \(b\), \(c\), and \(d\) can only take the values \(1\) and \(-1\). Therefore, \(acd=a(ab)(ab)=aa^2b^2=a\) and \(bcd=b(ab)(ab)=ba^2b^2=b\). We now have the following simpler and completely general version of the first three columns of a \(2\times \infty\) Griffin Grid.
In the same way that the third column was computed from the first and second columns, we can compute the fourth column from the second and third columns. After doing this, we get the diagram below. There is a thick vertical line separating the first three columns from the rest of the \(2\times\infty\) grid.
Consider the six cells to the left of the thick line as a \(2\times 3\) grid. The four integers in the first two columns are equal to the products of their neighbours by construction. Denote by \(C\) the cell in the first row and the third column. The integer in \(C\) is \(a\). By construction, the \(1\) to its right has been chosen so that the product of the neighbourhood of \(C\), including the \(1\) to its right, is \(1\). However, this means the product of the cells in its neighbourhood that are to the left of the vertical line is also equal to \(1\) (since \(1\) divided by \(1\) is \(1\)). These three cells (left of \(C\), below \(C\), and \(C\) itself) contain integers that have a product of \(1\).
A similar argument can be used on the cell below \(C\) to confirm that the \(2\times 3\) grid to the left of the thick line is a Griffin Grid. This is completely independent of the choice of \(a\) and \(b\). There are two possibilities for each of \(a\) and \(b\), so there are \(2\times 2=4\) Griffin Grids of size \(2\times 3\). They are
This approach can be generalized to determine the number of \(2\times n\) Griffin Grids. To explain this, we first continue to fill out a few more columns in the \(2\times \infty\) grid. We will call the Griffin Grid filled in by starting with variables in the first column and letting them propagate in the way described above the \(2\times \infty\) variable Griffin Grid.
By similar reasoning to before, the first \(n\) columns of a \(2\times \infty\) Griffin Grid will form a \(2\times n\) Griffin Grid exactly when both integers in the \((n+1)\)st column equal \(1\). If we examine the \(2\times \infty\) variable Griffin Grid, the number of ways to assign values to \(a\) and \(b\) so that both integers in the \((n+1)\)st column are \(1\) will be equal to the number of \(2\times n\) Griffin Grids.
For example, to count the \(2\times 5\) Griffin Grids, we look at the \(6\)th column of the \(2\times\infty\) variable Griffin Grid. Both cells contain \(ab\). Thus, the first five columns form a \(2\times 5\) Griffin Grid if and only if \(ab=1\). This happens when \(a=b=1\) and when \(a=b=-1\), so there are exactly two \(2\times 5\) Griffin Grids. Similarly, to count \(2\times 4\) Griffin Grids, we count the number of ways to choose \(a\) and \(b\) so that the \(5\)th column of the \(2\times \infty\) variable Griffin Grid contains only \(1\). The \(5\)th column contains \(a\) and \(b\), so we get a \(2\times 4\) Griffin Grid only when \(a=b=1\). Thus, there is exactly one \(2\times 4\) Griffin Grid.
Now notice that the columns of the \(2\times \infty\) variable Griffin Grid appear to repeat. Indeed, since each column after the second is computed from the previous two columns, as soon as a pair of two consecutive columns appears for a second time, the columns must repeat. The first and second columns are identical to the fifth and sixth columns, so the columns in the \(2\times \infty\) variable Griffin Grid must repeat with period \(4\). This means the number of \(2\times n\) Griffin Grids is always the same as the number of \(2\times(n+4)\) Griffin Grids.
The number of \(2\times 1\) Griffin Grids is \(2\) (this can be seen using the method described above). The number of \(2\times 2\) Griffin Grids is \(1\) (this was noted earlier but can also be checked using the method described above). The number of \(2\times 3\) Griffin Grids is \(4\), and the number of \(2\times 4\) Griffin Grids is \(1\). This repeats, so we get the following:
If \(n\) is even, then there is only one \(2\times n\) Griffin Grid.
If \(n\) is one more than a multiple of \(4\), then there are two \(2\times n\) Griffin Grids.
If \(n\) is three more than a multiple of \(4\), then there are four \(2\times n\) Griffin Grids.
As with \(2\times n\) Griffin Grids, we can fill in the \(3\times \infty\) variable Griffin Grid starting with \(a\), \(b\), and \(c\) in the first column. As before, we can assume \(a^2=b^2=c^2=1\). Filling out subsequent columns until we see a repetition, we get the following:
To determine the number of \(3\times 1\) Griffin Grids, we need to find all ways to choose \(a\), \(b\), and \(c\) so that the integers in the second column are all \(1\). In other words, we need all solutions to the system of \[\begin{align*} ab &= 1 \\ abc &=1 \\ bc &= 1\end{align*}\] where \(a\), \(b\), and \(c\) are all \(\pm 1\).
The equations \(ab=1\) and \(abc=1\) can be multiplied to get \(ababc=1\) or \(a^2b^2c=1\), so \(c=1\). We can multiply this equation by \(bc=1\) to get \(bc^2=1\) or \(b=1\). Finally, multiplying \(bc=1\) by \(abc=1\) gives \(ab^2c^2=1\) so \(a=1\). This method of solving probably seems unnecessarily complicated, but it generalizes nicely. We have shown that the only solution to the system is \(a=b=c=1\). Therefore, there is only one \(3\times 1\) Griffin Grid.
To determine the number of \(3\times 2\) Griffin Grids, we need to count the number of ways to choose \(a\), \(b\), and \(c\) to each be \(\pm 1\) so that the entries in the third column are all \(1\). The middle integer is always \(1\), so this cell is \(1\) regardless of how \(a\), \(b\), and \(c\) are chosen. The other two equations are both \(ac=1\), so this time the number of Griffin Grids is equal to the number of solutions to the system with just the equation \(ac=1\), where \(a\), \(b\), and \(c\) must all be \(\pm 1\).
This system does not restrict \(b\) beyond \(b=\pm 1\). For \(ac=1\), we need either \(a=c=1\) or \(a=c=-1\). This means there are \(2\times2=4\) solutions (\(2\) choices for \(b\) and two independent choices for the equal value of \(a\) and \(c\)). There are four \(3\times 2\) Griffin Grids.
Continuing in this way, we can count the number of Griffin Grids of size \(3\times n\) for \(n=1\) through \(n=12\). After that the number of Griffin Grids repeats with period \(12\). The number of \(3\times n\) Griffin Grids are summarized in the table below.
| \(\boldsymbol{n}\) | # of \(\boldsymbol{3\times n}\) Griffin Grids |
|---|---|
| \(1\), \(3\), \(4\), \(6\), \(7\), \(9\), \(10\), or \(12\) more than a multiple of \(12\) |
\(1\) |
| \(2\) or \(8\) more than a multiple of \(12\) | \(4\) |
| \(5\) or \(11\) more than a multiple of \(12\) | \(8\) |
Finally, we leave as an exercise that the number of Griffin Grids of size \(4\times n\) is \(16\) if \(n\) is a multiple of \(4\) and \(1\) otherwise.
Suppose \(x_1\), \(x_2\), , \(x_k\) are variables and \(P_1\), \(P_2\), \(P_r\) are each the product of some of the \(x_i\). By convention, we consider a single variable to be a product. For example, it might be that \(P_3=x_9\). We will also allow the \(P_i\) to be \(1\), the so-called "empty product". We will show that the number of solutions to the system \[\begin{align*} P_1 &= 1 \\ P_2 &= 1 \\ &\vdots \\ P_r &= 1\end{align*}\] is a power of \(2\), provided each \(x_i\) is restricted to the values \(1\) and \(-1\). Since each \(x_i=\pm1\), we have that \(x_i^2=1\), so we can assume that no equation mentions a variable more than once. Following the work from part (b), the number of \(m\times n\) Griffin Grids is always equal to the number of solutions to such a system of equations, so this will prove that the number of Griffin Grids is always a power of \(2\).
The key observation is the following: For any \(i\) with \(1\leq i\leq r\), the system of equations above has the exact same set of solutions as the system \[\begin{align*} P_1 &= 1 \\ P_2 &= 1 \\ &\vdots \\ P_{i-1} &= 1 \\ P_1P_i &= 1 \\ P_{i+1} &= 1 \\ &\vdots \\ P_r &= 1\end{align*}\] That is, if we modify the system by multiplying one equation by another equation, the solution set does not change. To see why this is true, we first suppose that \((x_1,x_2,\dots,x_m)=(c_1,c_2,\dots,c_m)\) is a solution to the original system. Every equation in the second system appears in the original system except \(P_1P_i=1\), so all equations in the second system except \(P_1P_i=1\) are automatically satisfied by the choice of the \(x_i\). By assumption, \(P_1=1\) and \(P_i=1\), so we also have \(P_1P_i=1\) as well. We have confirmed that \((x_1,x_2,\dots,x_m)=(c_1,c_2,\dots,c_m)\) is a solution to the second system.
A nearly identical argument shows that a solution to the second system is also a solution to the first system, proving that the two systems have the exact same set of solutions.
We will now prove that the number of solutions is a power of \(2\) by induction on \(k\), the number of variables.
If \(k=1\), then the only possible equations are \(x_1=1\) and \(1=1\). If \(x_1=1\) appears, then there is one solution. If \(x_1=1\) does not appear, then all equations are \(1=1\), so the equations to not restrict the value of \(x_1\) beyond \(x_1=1\) and \(x_1=-1\). Therefore, the number of solutions is either \(1\) or \(2\), both of which is a power of \(2\).
Now suppose the number of solutions to such a system of equations in at most \(k-1\) variables is always a power of \(2\).
Consider a system of equations in \(k\) variables, \(x_1\) through \(x_k\). If it happens to be that none of the equations mention \(x_k\), then the system can be viewed as having at most \(k-1\) variables. By induction, the number of solutions to this system (with \(x_k\) ignored) is a power of \(2\). That is, the number of ways to choose values of \(x_1\) through \(x_{k-1}\) so that the equations are all satisfied is \(2^d\) for some non-negative integer \(d\).
Since \(x_k\) is not mentioned in the equations, every one of these \(2^d\) solutions allows us to choose \(x_k=1\) or \(x_k=-1\). Therefore, the system has \(2\times 2^d=2^{d+1}\) solutions.
Now suppose \(x_k\) appears in at least one equation. By possibly reordering the equations, we can assume that \(P_1=1\) mentions the variable \(x_k\). Consider the system \[\begin{align*} P_1 &= 1 \\ Q_2 &= 1 \\ Q_3 &= 1 \\ &\vdots \\ Q_r &= 1\end{align*}\] where \(Q_i=P_i\) if \(P_i\) does not mention \(x_k\), and \(Q_i=P_1P_i\) if \(P_i\) mentions \(x_k\). In other words, equations from \(P_2\) through \(P_r\) that mention \(x_k\) get multiplied by \(P_1\) and the others are left alone. From earlier, the new system has the same solutions as the original system.
If \(P_i\) mentions \(x_k\), then it must mention it exactly once. This means the equation \(Q_i=1\) mentions \(x_k\) exactly twice, but these occurrences can be deleted since \(x_k^2=1\).
The point is that we have converted the given system to a new system that has the same solution set and \(P_1=1\) is the only equation that mentions \(x_k\). Now consider the system \[\begin{align*} Q_2 &= 1 \\ Q_3 &= 1 \\ &\vdots \\ Q_r &= 1\end{align*}\] which does not mention \(x_k\). By induction, the number of solutions to this system is \(2^d\) for some non-negative integer \(d\). Each such solution to this smaller system is an assignment of values to the variables \(x_1\) through \(x_{k-1}\). Once these values are chosen, the equation \(P_1=1\), which mentions \(x_k\), will determine the value of \(x_k\).
Therefore, the number of solutions to the original system is \(2^d\). Using induction, we have now shown that the number of solutions to any system of this type is a power of \(2\). Therefore, the number of \(m\times n\) Griffin Grids is always a power of \(2\).
Finally, note that the system arising from the \(m\times\infty\) variable Griffin Grid always has \(m\) variables. There are at most \(2^m\) ways to assign a value of \(1\) or \(-1\) to each variable, so the number of solutions must be a power of \(2\) that is at most \(2^m\).
No solution provided.
Once again, we imagine filling in the \(m\times\infty\) variable Griffin Grid starting with variables \(a_1, a_2,\dots, a_m\) in the first column.
Every cell in the grid contains either \(1\) or the product of some of \(a_1\) through \(a_m\), where each variable appears at most once in such a product. There are exactly \(2^m\) possible expressions that can go in the cells. In any two consecutive columns, there are \(2n\) cells, which means there are \((2^m)^{2n}=2^{2mn}\) possible ways that the \(2n\) cells in two consecutive columns can be filled. In practice, not all of these possibilities will actually occur.
Among the first \(2^{2mn}+2\) columns, there are \(2^{2mn}+1\) pairs of consecutive columns, which means there must be two pairs of consecutive columns that are identical.
Since there are two identical pairs of consecutive columns, we can choose the earliest ones. More precisely, let \(i\) be the smallest positive integer such that there is \(j>i\) with the property that the \(i\)th column equals the \(j\)th column and the \((i+1)\)st column equals the \((j+1)\)st column.
Suppose that \(i>1\). Let \(P_1, P_2,\ldots,P_m\) be the products in column \(i-1\) let \(Q_1, Q_2,\ldots,Q_m\) be the products in column \(i\), and let \(R_1, R_2,\ldots,R_m\) be the products in column \(i+1\).
By construction, we have that \(R_1=P_1Q_1Q_2\) (after possibly removing the squares of some variables). This equation can be multiplied on both sides by \(Q_1Q_2\) to get the equation \(R_1Q_1Q_2=P_1(Q_1)^2(Q_2)^2\). Since the square of every variable in \(Q_1\) and \(Q_2\) is \(1\), we also have \((Q_1)^2=(Q_2)^2=1\), so \(P_1=Q_1Q_2R_1\).
We also have that \(R_2=P_2Q_1Q_2Q_3\), and it similarly follows that \(P_2=Q_1Q_2Q_3R_2\).
Continuing in this way, we get that each \(P_i\) can be computed in terms of the \(Q_i\) and \(R_i\). In other words, column \(i-1\) can be computed directly from columns \(i\) and \(i+1\).
Because of our assumptions about \(i\) and \(j\), it follows that column \(i-1\) must be equal to column \(j-1\). However, this means columns \(i-1\) and \(i\) are identical to columns \(j-1\) and \(j\), which contradicts the minimality of \(i\).
We conclude that \(i>1\) is impossible, so it must be that \(i=1\) which means column \(j\) equals column \(1\) and column \(j+1\) equals column \(2\).
Therefore, the products in column \(j\) are all single variables, and in fact, they are the variables \(a_1\), \(a_2\), , \(a_m\) in order from top to bottom. The only way to assign the variables so that the entire column contains \(1\) is to set \(a_1=1\), \(a_2=1\), and so on to \(a_m=1\). Therefore, there is exactly one \(m\times (j-1)\) Griffin Grid.
Most of the work was done in part (e). Let’s assume that column \(j>1\) equals column \(1\) and column \(j+1\) equals column \(2\). Thus, we are assuming that the entries in column \(j\) are \(a_1\), \(a_2\), , \(a_m\) from top to bottom and that the entries in column \(j+1\) are \(a_1a_2\), \(a_1a_2a_3\), \(a_2a_3a_4\), , \(a_{m-2}a_{m-1}a_m\), \(a_{m-1}a_m\) from top to bottom.
Suppose that \(P_1\), \(P_2\), , \(P_m\) are the products in column \(j-1\). The top cell in column \(j+1\) contains \(a_1a_2\) since column \(j+1\) equals column \(2\). The expression must also be \(a_1a_2P_1\) by the way the \(m\times\infty\) variable Griffin Grid is filled in. From \(a_1a_2=a_1a_2P_1\), we get \(P_1=1\).
Looking at the second cell in column \(j+1\), we have that it is equal to \(a_1a_2a_3\), but it is also equal to \(P_2a_1a_2a_3\), and so \(P_2=1\).
Continuing in this way, we get that every entry in column \(j-1\) equals \(1\). Since any assignment of values to \(a_1\), \(a_2\), , \(a_m\) will lead to column \(j-1\) having all \(1\)s, we conclude that there are \(2^m\) Griffin Grids of size \(m\times(j-2)\). As a final note, observe that column 1 and column 2 always (for every \(m\)) contain products that are not equal to \(1\), so we know that \(j-1>2\), from which it follows that \(j-2>1\). This means we do not need to worry about the possibility that \(j-2=0\).
No solution provided.