Painting by Numbers

(This is Lucas.) Hi guys. It's been a long couple weeks (for those who are still active students, at least), let's wind down with some combi. In this post, I'll try to (at least partially) de-mystify colouring/invariants. As always, I'd encourage those of you who are still students to try the questions yourself to get a feel for them before reading the explanations that follow. 

Question 1

Each cell of a 726 by 726 grid is initially filled with a "$+1$". In a move, we may flip the signs of a 3 by 3 grid of our choice, less two opposite corners (so we flip 7 cells in each move). Can we reach a state where every cell contains a "$-1$"?

Effectively, we affect 7 cells in this formation (or its reflection).

Initial Thoughts

The setup is practically begging us to apply some colouring. However, the usual suspects don't yield any results, and thinking broadly it's hard to imagine a coloring applying nicely to a set of 7 cells. 

Maybe we can play around with the operation a bit...

Makin' Moves

Let's fiddle around with the given move and see what's possible. Specifically, our goal is to combine moves to have a small effect. 

With this goal in mind, we quickly realize we can toggle a $2 \times 2$ square, as long as it does not touch the border of the grid, as follows: 

The diagrams only get worse from here.

As a result, we can actually toggle an individual cell, as long as it is in the center of a $5 \times 5$ grid: 

What does this mean? Well, we can effectively ignore all cells except for the outer 2 layers, since they can be toggled individually! 

Now that we know where to focus our attention...

Cashing In

Let's complete the proof. Of course, we assume for the sake of contradiction that flipping the entire board is possible. 

Consider the bottom row. Any move that affects it must affect 2 consecutive cells. In particular, if we take every other cell (so 363 in total), every move affecting the bottom row must affect exactly 1 of these cells. As such, there most be an odd number of such moves in all. 

Now, consider the second row from the bottom. Each aforementioned move affects 3 of these cells. Thus, overall they affect an odd number of these cells. However, each other move only affects either 2 or 0 of these cells, thus we cannot flip this entire row from $+1$ to $-1$. 

Contradiction! 

To put the proof in concise terms, consider the following 1089 shaded cells: 

We take every other cell along the bottom row, and every cell in the row immediately above.

Each move flips either 0, 2, or 4 of these cells, implying that at any time their product is $+1$. However, in the desired end state their product is $-1$, hence it is unreachable. 

Hopefully you can see that this seemingly obscure and niche colouring is actually 'hinted' at by our observations from playing around with the operation. Let's take a look at how a similar approach can be applied to a different question.

Question 2

(SMO Senior 2013) An integer is written in each cell of a $6 \times 6$ grid as shown below. In a move, we may choose a $k \times k$ subgrid ($1 < k \leq 6$) and add 1 to all its entries. Is it possible to perform finitely many of these operations to end up with all entries in the grid being divisible by 3?

Initial Thoughts

Once again, the setup of the question heavily suggests we are looking for an invariant. We can imagine assigning weights to the squares such that each subgrid sums to a multiple of 3. Then, it suffices to consider the sum $\sum_{1 \leq i,j \leq 6}v_{i,j}w_{i,j}$ where $v_{i,j},w_{i,j}$ refer to the value and weight of cell $(i,j)$ respectively. Since the value of this sum (mod 3) will be unaffected by any move, if the start and end states have different values (mod 3) we win. 

However, as before, the usual suspects for how to weight the grid fail (For instance, quick-minded students may think of alternating $+1$ and $-1$ weights in each row, which works for every size subgrid - except $5 \times 5$). As such, we need a more targeted approach...

No Sudden Movements

Again, let's try to combine moves to achieve a minimal 'net footprint' (i.e. affect as few cells as possible overall). 

Quickly, we may notice that as before, we can change the center cell of a $5 \times 5$ subgrid without affecting any other cell: 

Moving on these 4 subgrids and then the large 5 × 5 twice achieves the desired result.

As such, we should 'ignore' (i.e. assign a weight of 0 to) the 4 central cells when constructing our invariant. 

Digging a bit further, we find that we can add 1 to 2 opposite corners of an $n \times n$ subgrid, where $n \geq 4$: 

Here, we operate on the blue and red square, then the two green squares twice each.

Thinking about our invariant idea, this implies any such pair of cells should have weights summing to 0. In particular, we can infer that the cells along the diagonals should have weights of 0. 

Now, by considering $2 \times 2$ subgrids as well as pairs of cells affected by the above combination, we can infer the full colouring required (up to multiplication by -1): 

Checking, the cells affected by any given move have weights summing to a multiple of 3, as desired! Checking the initial board state given, the sum of $(weight \times value)$ over all cells is not a multiple of 3, so we are done.

Conclusion

In conclusion, while combi has no shortage of 'magical' ideas, they seldom truly come out of nowhere - often, we can (at least indirectly) link these ideas to our observations.