When can we flip the entire grid if we contunue flipping the cells of a subgrid?

88 Views Asked by At

Consider a 50-by-50 square grid. Initially all cells have the number $0$. For each operation, one selects a 1-by-7 or 7-by-1 subgrid and changes the number in the cells of the subgrid from 1 to 0 and from 0 to 1. Is it possible that after a number of operations, all cells have the number $1$.

Context: I remembered that I saw a similar question somewhere (but I cannot remember exactly where). In that question, each operation flips 2-by-2 subgrid. I am interested in this question, but want to do things generally, i.e., to find the general conditions on the size of the square grid and the size of the subgrid, and I thought starting with subgrids of 1-by-m and m-by-1 would be easier.)

I am also wondering whether there is any conclusion if we generalize $50$ to $n$ and $7$ to $m$?

1

There are 1 best solutions below

0
On BEST ANSWER

Color the grid in the usual checkerboard pattern using $7$ colors. Note that there is an obvious way to flip $2499$ of the $2500$ squares —- all except one corner. Flip all of the squares of a $49 \times 49$ grid ($343$ moves), and then flip as many squares as possible along the remaining row and column (another $14$ moves). Since each move flips one square of each color, we have flipped $357$ squares of each color, with one square left over. This means one color is applied to $358$ squares and the other six colors are applied to $357$ squares each.

Now consider the parity of the number of $1$s of each color. At the start of the process, all colors have the same parity —- even, because there are no $1$s. If we can flip the entire grid, we’ve just demonstrated that there will be colors of both parities —- one color will have an even number of $1$s and the other six colors will have an odd number of $1$s.

But that’s not possible. Each permitted move changes the parity of all seven colors. All $7$ colors started out with the same parity, so they will always have the same parity. Thus, you can’t flip the entire grid.

Edited to add: This proof generalizes to show that an $n \times n$ grid can't be flipped using blocks of $k$ horizontally or vertically connected squares unless $k \mid n$. That's because a similar construction (using $k$ colors to color the grid) leaves you with an $m \times m$ unflipped block in the corner where $m \equiv n \pmod k$, and $m \lt k$. The main diagonal of the unflipped block will have a different parity from the color used on each of the adjacent diagonals, and since $m \lt k$ two of those adjacent diagonals will be the only squares colored in one of the colors.

Obviously, if $k \mid n$, then the grid can be flipped in an obvious way.