CEMC Banner

Problem of the Month
Solution to Problem 8: May 2024

  1. Suppose an m×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=a2=1, since 12=(1)2=1.

    Now suppose an m×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=±1 and b=±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.

  2. Using similar reasoning to that which was used in part (a), it can be shown that an m×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×n grid with 1 or 1 in every cell, there are only four possibilities for the first column. They are shown below.

    1 and 1, or 1 and negative 1, or negative 1 and 1, or negative 1 and negative 1.

    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× 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:

    The two cells in the first column and the top cell in the second column are highlighted. The two cells in the first column and the bottom cell in the second column are highlighted.

    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:

    First column: 1 and 1. Second column: 1 and 1. First column: 1, negative 1. Second column: negative 1, negative 1. First column: negative 1, 1. Second column: negative 1, negative 1. First column: negative 1, negative 1. Second column: 1, 1.

    From here, we can see that there is exactly one 2×2 Griffin Grid. This is because there are only four possible ways to fill in the first column, and if a 2×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×2 grids gives a Griffin Grid.

    Continuing in this way, we can examine 2×3 Griffin Grids by filling in the next column. This can be done using the neighbourhoods shown below.

    The first three cells in the top row and the second cell in the bottom row are highlighted. The first three cells in the bottom row and the second cell in the top row are highlighted.

    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.

    First column: a then b. Second column: c then d. Third column: acd then bcd.

    However, we can simplify this a little bit. From earlier, we know that c=d=ab. As well, a2=b2=c2=d2=1 since each of the variables a, b, c, and d can only take the values 1 and 1. Therefore, acd=a(ab)(ab)=aa2b2=a and bcd=b(ab)(ab)=ba2b2=b. We now have the following simpler and completely general version of the first three columns of a 2× Griffin Grid.

    First column: a then b. Second column: ab then ab. Third column: a then b.

    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× grid.

    The fourth column is 1, 1.

    Consider the six cells to the left of the thick line as a 2×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×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×2=4 Griffin Grids of size 2×3. They are

    All 1s in the grid. First column: 1, negative 1. Second column: negative 1, negative 1. Third column: 1, negative 1. First column: negative 1, 1. Second column: negative 1, negative 1. Third column: negative 1, 1. First column: negative 1, negative 1. Second column: 1, 1. Third column: negative 1, negative 1.

    This approach can be generalized to determine the number of 2×n Griffin Grids. To explain this, we first continue to fill out a few more columns in the 2× 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× variable Griffin Grid.

    The first four columns, in terms of a and b, are as previously described. the next four columns are identical to the first four and this pattern continues.

    By similar reasoning to before, the first n columns of a 2× Griffin Grid will form a 2×n Griffin Grid exactly when both integers in the (n+1)st column equal 1. If we examine the 2× 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×n Griffin Grids.

    For example, to count the 2×5 Griffin Grids, we look at the 6th column of the 2× variable Griffin Grid. Both cells contain ab. Thus, the first five columns form a 2×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×5 Griffin Grids. Similarly, to count 2×4 Griffin Grids, we count the number of ways to choose a and b so that the 5th column of the 2× variable Griffin Grid contains only 1. The 5th column contains a and b, so we get a 2×4 Griffin Grid only when a=b=1. Thus, there is exactly one 2×4 Griffin Grid.

    Now notice that the columns of the 2× 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× variable Griffin Grid must repeat with period 4. This means the number of 2×n Griffin Grids is always the same as the number of 2×(n+4) Griffin Grids.

    The number of 2×1 Griffin Grids is 2 (this can be seen using the method described above). The number of 2×2 Griffin Grids is 1 (this was noted earlier but can also be checked using the method described above). The number of 2×3 Griffin Grids is 4, and the number of 2×4 Griffin Grids is 1. This repeats, so we get the following:

    1. If n is even, then there is only one 2×n Griffin Grid.

    2. If n is one more than a multiple of 4, then there are two 2×n Griffin Grids.

    3. If n is three more than a multiple of 4, then there are four 2×n Griffin Grids.

    As with 2×n Griffin Grids, we can fill in the 3× variable Griffin Grid starting with a, b, and c in the first column. As before, we can assume a2=b2=c2=1. Filling out subsequent columns until we see a repetition, we get the following:

    A description of the grid follows.

    To determine the number of 3×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 ab=1abc=1bc=1 where a, b, and c are all ±1.

    The equations ab=1 and abc=1 can be multiplied to get ababc=1 or a2b2c=1, so c=1. We can multiply this equation by bc=1 to get bc2=1 or b=1. Finally, multiplying bc=1 by abc=1 gives ab2c2=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×1 Griffin Grid.

    To determine the number of 3×2 Griffin Grids, we need to count the number of ways to choose a, b, and c to each be ±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 ±1.

    This system does not restrict b beyond b=±1. For ac=1, we need either a=c=1 or a=c=1. This means there are 2×2=4 solutions (2 choices for b and two independent choices for the equal value of a and c). There are four 3×2 Griffin Grids.

    Continuing in this way, we can count the number of Griffin Grids of size 3×n for n=1 through n=12. After that the number of Griffin Grids repeats with period 12. The number of 3×n Griffin Grids are summarized in the table below.

    n # of 3×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×n is 16 if n is a multiple of 4 and 1 otherwise.

  3. Suppose x1, x2, , xk are variables and P1, P2, Pr are each the product of some of the xi. By convention, we consider a single variable to be a product. For example, it might be that P3=x9. We will also allow the Pi to be 1, the so-called "empty product". We will show that the number of solutions to the system P1=1P2=1Pr=1 is a power of 2, provided each xi is restricted to the values 1 and 1. Since each xi=±1, we have that xi2=1, so we can assume that no equation mentions a variable more than once. Following the work from part (b), the number of m×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 1ir, the system of equations above has the exact same set of solutions as the system P1=1P2=1Pi1=1P1Pi=1Pi+1=1Pr=1 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 (x1,x2,,xm)=(c1,c2,,cm) is a solution to the original system. Every equation in the second system appears in the original system except P1Pi=1, so all equations in the second system except P1Pi=1 are automatically satisfied by the choice of the xi. By assumption, P1=1 and Pi=1, so we also have P1Pi=1 as well. We have confirmed that (x1,x2,,xm)=(c1,c2,,cm) 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 x1=1 and 1=1. If x1=1 appears, then there is one solution. If x1=1 does not appear, then all equations are 1=1, so the equations to not restrict the value of x1 beyond x1=1 and x1=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 k1 variables is always a power of 2.

    Consider a system of equations in k variables, x1 through xk. If it happens to be that none of the equations mention xk, then the system can be viewed as having at most k1 variables. By induction, the number of solutions to this system (with xk ignored) is a power of 2. That is, the number of ways to choose values of x1 through xk1 so that the equations are all satisfied is 2d for some non-negative integer d.

    Since xk is not mentioned in the equations, every one of these 2d solutions allows us to choose xk=1 or xk=1. Therefore, the system has 2×2d=2d+1 solutions.

    Now suppose xk appears in at least one equation. By possibly reordering the equations, we can assume that P1=1 mentions the variable xk. Consider the system P1=1Q2=1Q3=1Qr=1 where Qi=Pi if Pi does not mention xk, and Qi=P1Pi if Pi mentions xk. In other words, equations from P2 through Pr that mention xk get multiplied by P1 and the others are left alone. From earlier, the new system has the same solutions as the original system.

    If Pi mentions xk, then it must mention it exactly once. This means the equation Qi=1 mentions xk exactly twice, but these occurrences can be deleted since xk2=1.

    The point is that we have converted the given system to a new system that has the same solution set and P1=1 is the only equation that mentions xk. Now consider the system Q2=1Q3=1Qr=1 which does not mention xk. By induction, the number of solutions to this system is 2d for some non-negative integer d. Each such solution to this smaller system is an assignment of values to the variables x1 through xk1. Once these values are chosen, the equation P1=1, which mentions xk, will determine the value of xk.

    Therefore, the number of solutions to the original system is 2d. 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×n Griffin Grids is always a power of 2.

    Finally, note that the system arising from the m× variable Griffin Grid always has m variables. There are at most 2m 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 2m.

  4. No solution provided.

  5. Once again, we imagine filling in the m× variable Griffin Grid starting with variables a1,a2,,am in the first column.

    Every cell in the grid contains either 1 or the product of some of a1 through am, where each variable appears at most once in such a product. There are exactly 2m possible expressions that can go in the cells. In any two consecutive columns, there are 2n cells, which means there are (2m)2n=22mn 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 22mn+2 columns, there are 22mn+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 ith column equals the jth column and the (i+1)st column equals the (j+1)st column.

    Suppose that i>1. Let P1,P2,,Pm be the products in column i1 let Q1,Q2,,Qm be the products in column i, and let R1,R2,,Rm be the products in column i+1.

    By construction, we have that R1=P1Q1Q2 (after possibly removing the squares of some variables). This equation can be multiplied on both sides by Q1Q2 to get the equation R1Q1Q2=P1(Q1)2(Q2)2. Since the square of every variable in Q1 and Q2 is 1, we also have (Q1)2=(Q2)2=1, so P1=Q1Q2R1.

    We also have that R2=P2Q1Q2Q3, and it similarly follows that P2=Q1Q2Q3R2.

    Continuing in this way, we get that each Pi can be computed in terms of the Qi and Ri. In other words, column i1 can be computed directly from columns i and i+1.

    Because of our assumptions about i and j, it follows that column i1 must be equal to column j1. However, this means columns i1 and i are identical to columns j1 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 a1, a2, , am in order from top to bottom. The only way to assign the variables so that the entire column contains 1 is to set a1=1, a2=1, and so on to am=1. Therefore, there is exactly one m×(j1) Griffin Grid.

  6. 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 a1, a2, , am from top to bottom and that the entries in column j+1 are a1a2, a1a2a3, a2a3a4, , am2am1am, am1am from top to bottom.

    Suppose that P1, P2, , Pm are the products in column j1. The top cell in column j+1 contains a1a2 since column j+1 equals column 2. The expression must also be a1a2P1 by the way the m× variable Griffin Grid is filled in. From a1a2=a1a2P1, we get P1=1.

    Looking at the second cell in column j+1, we have that it is equal to a1a2a3, but it is also equal to P2a1a2a3, and so P2=1.

    Continuing in this way, we get that every entry in column j1 equals 1. Since any assignment of values to a1, a2, , am will lead to column j1 having all 1s, we conclude that there are 2m Griffin Grids of size m×(j2). 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 j1>2, from which it follows that j2>1. This means we do not need to worry about the possibility that j2=0.

  7. No solution provided.