Problem of the Month Solution to Problem 8: May 2024
Suppose an grid
with a or in every cell is a Griffin Grid.
Consider an arbitrary cell and
suppose it contains the integer
(so or ). Let be the product of the integers in the
neighbours of . Since the grid is
a Griffin Grid, we have . The
product of the integers in the neighbourhood of is , since .
Now suppose an grid
has a or a in every cell and that the product of
the integers in every neighbourhood is . Let be an arbitrary cell, let be the integer in , and let be the product of the integers in the
neighbours of . To verify that the
grid is a Griffin Grid, we need to show that .
We are assuming that , and
we know that and because it is the product of some
integers, all of which are either
or . If and were different, then their product
would be , not . Therefore, .
Using similar reasoning to that which was used in part (a), it
can be shown that an grid
with or 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 grid with or 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 rows and infinitely many
columns. We will refer to such a grid as a 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 Griffin Grid. This is because
there are only four possible ways to fill in the first column, and if a
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 grids gives a Griffin Grid.
Continuing in this way, we can examine 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 , , , and , 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 . As well, since each of the
variables , , , and can only take the values and . Therefore, and . We now have the
following simpler and completely general version of the first three
columns of a 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 grid.
Consider the six cells to the left of the thick line as a grid. The four integers in the
first two columns are equal to the products of their neighbours by
construction. Denote by the cell
in the first row and the third column. The integer in is . By construction, the to its right has been chosen so that
the product of the neighbourhood of , including the to its right, is . However, this means the product of the
cells in its neighbourhood that are to the left of the vertical line is
also equal to (since divided by is ). These three cells (left of , below , and itself) contain integers that have a
product of .
A similar argument can be used on the cell below to confirm that the grid to the left of the thick
line is a Griffin Grid. This is completely independent of the choice of
and . There are two possibilities for each
of and , so there are Griffin Grids of size . They are
This approach can be generalized to determine the number of Griffin Grids. To explain this,
we first continue to fill out a few more columns in the 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 variable Griffin
Grid.
By similar reasoning to before, the first columns of a Griffin Grid will form a
Griffin Grid exactly when
both integers in the st column equal . If we examine the variable Griffin Grid, the
number of ways to assign values to and so that both integers in the st column are will be equal to the number of Griffin Grids.
For example, to count the Griffin Grids, we look at the th column of the variable Griffin Grid. Both
cells contain . Thus, the first
five columns form a
Griffin Grid if and only if .
This happens when and when
, so there are exactly two
Griffin Grids. Similarly,
to count Griffin Grids,
we count the number of ways to choose and so that the th column of the variable Griffin Grid
contains only . The th column contains and , so we get a Griffin Grid only when . Thus, there is exactly one Griffin Grid.
Now notice that the columns of the 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
variable Griffin Grid must repeat with period . This means the number of Griffin Grids is always the
same as the number of
Griffin Grids.
The number of Griffin
Grids is (this can be seen using
the method described above). The number of Griffin Grids is (this was noted earlier but can also be
checked using the method described above). The number of Griffin Grids is , and the number of Griffin Grids is . This repeats, so we get the
following:
If is even, then there is
only one Griffin
Grid.
If is one more than a
multiple of , then there are two
Griffin Grids.
If is three more than a
multiple of , then there are four
Griffin Grids.
As with Griffin Grids,
we can fill in the
variable Griffin Grid starting with , , and in the first column. As before, we can
assume . Filling out
subsequent columns until we see a repetition, we get the following:
A grid with three rows and the leftmost fourteen columns filled in. Each entry is either an expression in variables ,
, and , or the number . The entries are given in the following
table with three rows and fourteen columns:
To determine the number of Griffin Grids, we need to find all ways to choose , , and so that the integers in the second
column are all . In other words,
we need all solutions to the system of where , , and are all .
The equations and can be multiplied to get or , so . We can multiply this equation by
to get or . Finally, multiplying by gives so . This method of solving probably
seems unnecessarily complicated, but it generalizes nicely. We have
shown that the only solution to the system is . Therefore, there is only one
Griffin Grid.
To determine the number of Griffin Grids, we need to count the number of ways to choose
, , and to each be so that the entries in the third
column are all . The middle
integer is always , so this cell
is regardless of how , , and are chosen. The other two equations are
both , so this time the number
of Griffin Grids is equal to the number of solutions to the system with
just the equation , where , , and must all be .
This system does not restrict
beyond . For , we need either or . This means there are solutions ( choices for and two independent choices for the
equal value of and ). There are four Griffin Grids.
Continuing in this way, we can count the number of Griffin Grids of
size for through . After that the number of Griffin
Grids repeats with period . The
number of Griffin Grids
are summarized in the table below.
# of Griffin Grids
, , , , , , , or more than a multiple of
or more than a multiple of
or more than a multiple of
Finally, we leave as an exercise that the number of Griffin Grids of
size is if is a multiple of and otherwise.
Suppose , , , are variables and , , are each the product of some of the
. By convention, we consider a
single variable to be a product. For example, it might be that . We will also allow the to be , the so-called "empty product". We will
show that the number of solutions to the system is a power of , provided each is restricted to the values and . Since each , we have that , so we can assume that no
equation mentions a variable more than once. Following the work from
part (b), the number of
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 .
The key observation is the following: For any with , the system of equations above has the exact same set
of solutions as the system 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
is a solution to the original system. Every equation in the second
system appears in the original system except , so all equations in the second
system except are
automatically satisfied by the choice of the . By assumption, and , so we also have as well. We have confirmed that
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 by induction on , the number of variables.
If , then the only possible
equations are and . If appears, then there is one
solution. If does not appear,
then all equations are , so the
equations to not restrict the value of beyond and . Therefore, the number of
solutions is either or , both of which is a power of .
Now suppose the number of solutions to such a system of equations in
at most variables is always a
power of .
Consider a system of equations in variables, through . If it happens to be that none of the
equations mention , then the
system can be viewed as having at most variables. By induction, the number
of solutions to this system (with ignored) is a power of . That is, the number of ways to choose
values of through so that the equations are all
satisfied is for some
non-negative integer .
Since is not mentioned in
the equations, every one of these solutions allows us to choose or . Therefore, the system has solutions.
Now suppose appears in at
least one equation. By possibly reordering the equations, we can assume
that mentions the variable
. Consider the system where if does not mention , and if mentions . In other words, equations from through that mention get multiplied by and the others are left alone. From
earlier, the new system has the same solutions as the original
system.
If mentions , then it must mention it exactly
once. This means the equation
mentions exactly twice, but
these occurrences can be deleted since .
The point is that we have converted the given system to a new system
that has the same solution set and is the only equation that mentions
. Now consider the system which does not mention . By induction, the number of
solutions to this system is for
some non-negative integer . Each
such solution to this smaller system is an assignment of values to the
variables through . Once these values are chosen,
the equation , which mentions
, will determine the value of
.
Therefore, the number of solutions to the original system is . Using induction, we have now shown
that the number of solutions to any system of this type is a power of
. Therefore, the number of Griffin Grids is always a power
of .
Finally, note that the system arising from the variable Griffin Grid
always has variables. There are
at most ways to assign a value
of or to each variable, so the number of
solutions must be a power of that
is at most .
No solution provided.
Once again, we imagine filling in the variable Griffin Grid
starting with variables in the first column.
Every cell in the grid contains either or the product of some of through , where each variable appears at most
once in such a product. There are exactly possible expressions that can go in
the cells. In any two consecutive columns, there are cells, which means there are possible ways that the
cells in two consecutive columns
can be filled. In practice, not all of these possibilities will actually
occur.
Among the first
columns, there are 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 be the smallest positive integer such
that there is with the
property that the th
column equals the th
column and the st
column equals the st column.
Suppose that . Let be the products in column let be the products in column , and let be the products in column .
By construction, we have that (after possibly removing
the squares of some variables). This equation can be multiplied on both
sides by to get the equation
. Since
the square of every variable in
and is , we also have , so .
We also have that , and it similarly
follows that .
Continuing in this way, we get that each can be computed in terms of the and . In other words, column can be computed directly from columns
and .
Because of our assumptions about and , it follows that column must be equal to column . However, this means columns and are identical to columns and , which contradicts the minimality of
.
We conclude that is
impossible, so it must be that
which means column equals column
and column equals column .
Therefore, the products in column are all single variables, and in fact,
they are the variables , , , in order from top to bottom. The only
way to assign the variables so that the entire column contains is to set , , and so on to . Therefore, there is exactly one
Griffin
Grid.
Most of the work was done in part (e). Let’s assume that column
equals column and column equals column . Thus, we are assuming that the entries
in column are , , , from top to bottom and that the
entries in column are , , , , , from top to bottom.
Suppose that , , , are the products in column . The top cell in column contains since column equals column . The expression must also be by the way the variable Griffin Grid is
filled in. From ,
we get .
Looking at the second cell in column , we have that it is equal to , but it is also equal to , and so .
Continuing in this way, we get that every entry in column equals . Since any assignment of values to
, , , will lead to column having all s, we conclude that there are Griffin Grids of size . As a final note, observe
that column 1 and column 2 always (for every ) contain products that are not equal to
, so we know that , from which it follows that
. This means we do not need
to worry about the possibility that .