share
Mathematics$6\times 6$ grid problem
[+2] [3] Àlex Rodríguez
[2020-08-04 10:37:32]
[ combinatorics ]
[ https://math.stackexchange.com/questions/3779625/6-times-6-grid-problem ]

[Edited to be consistent with the version I proposed in an answer below, which the OP agreed contained the essence of the problem.--John Hughes]

Some months ago, one friend proposed me a problem that I still do not find the solution. That is:

"You have a $6\times 6$ grid ($36$ squares) with an integer in each cell. There are $5$ different operators: you can add one to each cell any $n\times n$ square inside this $6\times 6$ grid (where $n=2,3,4,5,6$).

Can you, using these operators as many times as you want, make all numbers of this grid be multiples of $3$?"

The first thought it comes to me was to put all numbers modulo $3$. Then, find some coloration such that using any operator there is an invariant modulo $3$, but I did not find any. Later, I thought that using an specific combination of operators I can add some quantity to one square, so it implies that this is possible. Again, I did not find any successful combination.

I surrender, but if anyone can tell me your solution (because I do not want to tell my friend I do not solve it hehe).

I don't understand this part: "you can add up one to and nxn square inside this 6x6 grid". Can you clarify what you mean? - Matti P.
(1) Welcome to MSE. " you can add up one to and nxn square inside this 6x6 grid (where n=2,3,4,5,6). " is a little puzzling. Can you perhaps illustrate with an example or two? For instance, I can't immediately understand why filling in the grid with all zeroes is not a solution. - John Hughes
See my "answer" below for an extended comment. - John Hughes
[+5] [2020-08-04 11:40:38] John Hughes [ACCEPTED]

Assuming my interpretation of the question is correct, the answer is "no, you cannot always make the grid consist of multiples of $3$.

The proof involves a little linear algebra. We'll do everything mod 3.

  1. The space of all "problems" is a 36-dimensional space, with a basis given by the 36 matrices each of which has a "1" in exactly one location (so that $E_{3, 5}$ is all zeroes except for a $1$ in the 3rd row, fifth column).

  2. If we have a grid $A$, an "operation" amounts to adding a matrix $Q$ to $A$, where $Q$ is all zeroes except for a $k \times k$ block of $1$s, where $k = 2, 3, 4, 5,$ or $6$. So "solving" a puzzle $A$ amounts to finding a sequence $Q_1, Q_2, \ldots, Q_n$ where $$ A + Q_1 + Q_2 + \ldots + Q_n = 0.$$ Letting $R_i = -Q_i$, this amounts to saying $$A = R_1 + \ldots + R_n.$$

  3. To rephrase the previous paragraph, the puzzle is "Given any matrix $A$, is there a linear combination of the 'operation/ matrices which equals $A$?" (Note that mod 3, $-Q_1 = 2Q_i$, so each $R_i$ is in fact a linear combination of "operation" matrices.) Said even better, is the span of all operation matrices, mod 3, equal to the 36-dimensional space of `problems'?

  4. As it happens, I wrote a little matlab program to generate all the operation matrices, and convert each one to a 36-vector (by reading off the columns one after another). That gave me $55$ vectors in a 36 dimensional space. And then I computed the rank of this $36 \times 55$ matrix, and it turns out to be $35$ (alas).

  5. It takes a little thinking to see that the fact that the dimension of the column space over the reals is 35 means that the dimension of the columns space over the integers mod 3 cannot be more than 35, but that's actually true. Hence there's some "problem" matrix $A$ that cannot be represented by a linear combination (mod 3) of "operation" matrices.


I was proceeding along the same lines, but it never occurred to me to compute the rank over the reals. If it had turned out to be of full rank, you would have had to compute the rank over $\mathbb{F}_3$, correct? - saulspatz
Yep. And the real-rank-handles-$F_3$-rank argument is actually a little bit subtle, since rational/irrational stuff enters into it. I wonder if this question is actually a problem from Kleins "Coding the Matrix", where I first saw the lights-out puzzle described via linear algebra. I don't have a copy handy to check, alas. The real truth about my solution is that Matlab makes it easy to check the rank, so I tried it and then reasoned backwards. :) - John Hughes
(1) BTW, the row-reduced echelon form of that matrix has a last row that's all zeroes; that should tell you a "problem" that's unsolvable. And given that observation, I've got a very short (and explicit) solution to the puzzle. But first I'm waiting for Klein to tell me whether this is a homework problem from his book or not. :) - John Hughes
I think I have a proof for a prime $p$ that doesn't seem very subtle. It's enough to show that we can reduce the matrix to row-echelon form of $\mathbb{R}$ using integer arithmetic. As we work on a column, if one of the nonzero pivots divides all the others, there's no problem. Otherwise, the gcd of the nonzero potential pivots is a linear combination of them, by repeated application of the extended Euclidean algorithm, so by scaling and addition of rows, we can get the gcd to be one of the potential pivots. Doesn't this work? - saulspatz
That sounds right, but I'm a little groggy, so I'm not certain. Your "gcd" argument sounds a lot like what's done in Smith Normal Form, if I remember correctly (although that does both row AND column reduction, I think). - John Hughes
This might be asking for too much, but can your program produce an element of this $36^{th}$ dimension (i.e. an "unsolvable puzzle")? - RSpeciel
(1) See my last answer. It shows that a matrix of zeroes with a single $1$ in the second row, first column, is an unsolvable puzzle. - John Hughes
1
[+2] [2020-08-04 16:52:03] John Hughes

First, consider everything mod three; second, define the "dot product" of two matrices to be $$ A \cdot B = \sum_{i,j = 1}^3 a_{ij} b_{ij} $$ i.e., the result of multiplying corresponding elements and summing up the result (mod three).

Let $K$ be the matrix

 0    -1     2    -2     1     0
 1     0    -1     1     0    -1
-2     1     0     0    -1     2
 2    -1     0     0     1    -2
-1     0     1    -1     0     1
 0     1    -2     2    -1     0

which I've written with minus-signs so that it's easy to verify that for every size-2 block matrix, $X$, (i.e., a $6 \times 6$ matrix that's mostly zeroes, but with a $2 \times 2$ block of $1$s) we have $$ K \cdot X = 0, $$ and the same holds when $X$ is a size-3, 4, 5, or 6 block matrix.

Now suppose that the matrix $U$ given by

 0     0     0     0     0     0
 1     0     0     0     0     0
 0     0     0     0     0     0
 0     0     0     0     0     0
 0     0     0     0     0     0
 0     0     0     0     0     0

had the property that $$ W = U + Q_1 + Q_2 + \ldots Q_n $$ where the $Q_i$ are block matrices of sizes $2,3,4,5,$ or $6$ and $W$ is a matrix of all zeroes. Then we'd have \begin{align} 0 &= W \cdot K \\ &= U \cdot K + Q_1 \cdot K + \ldots + Q_n \cdot K \\ &= 1 + 0 + \ldots + 0\\ & = 1, \end{align} which is a contradiction.

How did I come up with the matrix $K$? I looked for something whose dot product with all possible block matrices was zero; Matlab helped.


2
[+1] [2020-08-04 11:04:42] John Hughes

Clarficiation question, too long for a comment

Could the question actually be this?

Given an arbitrary $6 \times 6$ square of integers, you're allowed to perform "operations" (defined below) on the square as many times as you like. Can you, performing these operations, make all numbers be multiples of $3$, regardless of the values in the initial grid?

An "operation" consists of choosing any $2 \times 2, 3 \times 3, 4\times 4, 5 \times 5$, or $6 \times 6$ square within the grid, and adding $1$ to each of the numbers within that square.

For example, if the initial square is $$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 0 & 0 & 0 & 0 & 2 \\ 1 & 1 & 1 & 0 & \color{red}2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} $$ then by picking the $3 \times 3$ square centered at the red "2", we can transform this to $$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 0 & 0 & \color{blue}1 & \color{blue}1 & \color{blue}3 \\ 1 & 1 & 1 & \color{blue}1 & \color{blue}3 & \color{blue}1 \\ 0 & 0 & 0 & \color{blue}1 & \color{blue}1 & \color{blue}1 \\ \end{pmatrix} $$ where the blue entries indicate changed colors.

====

Is that a correct representation of the problem?


This is how I read the question, for what that's worth. - saulspatz
(1) Right..."any => and" is a pretty common typo. If you believe this is the right problem, then working mod 3, a considering only the "basis matrices" $E_{ij}$ as starting points seems like a good strategy. This feels like a mild generalization of the "lights out" puzzle game. - John Hughes
@JohnHughes Are you (by any chance) from the planet Vulcan? Did you put your finger tips on the screen to do a silicon-mind-meld? - user2661923
It helps to have been around for a lot of years. At some point, you start to feel that you've heard all possible questions, and all possible mis-phrasings of all possible questions. - John Hughes
Yes! that's exactly what I mean - Àlex Rodríguez
3