Combinatorics olympiad problem infinite board, two parts

Question

Grid the plane forming an infinite board. In each cell of this board, there is a lamp, initially turned off. A permitted operation consists of selecting a square of $3\times 3, 4\times 4$ or $5\times 5$ cells and changing the state of all lamps in that square (those that are off become on, and those that are on become off).

(a) Prove that for any finite set of lamps, it is possible to achieve, through a finite sequence of permitted operations, that those are the only lamps turned on on the board.

(b) Prove that if in a sequence of permitted operations only two out of the three square sizes are used, then it is impossible to achieve that at the end the only lamps turned on on the board are those in a $2 \times 2$ square.

I couldn't solve part b).

In a) you can change the state of a $9\times 9$ board using the $3\times 3$, then you change the same $9\times 9$ board using 2 $4\times 4$ boards and 2 $5\times 5$ boards such that the $5 \times 5$ boards share a square. Therefore we changed the state of only one lamp, and this is enough to prove part a). (If this solution to part a) is not well understood, you can answer it in the comments and I will clarify it better).
Moons are the $5\times 5$ and elephants the $4\times 4$

I tried part b for a long time but I have no ideas how I can get it.

Answer 1

For part b, the idea is that we want to find an invariant doesn't affects 2 of those squares, but impacts the $2\times 2$ square.

---

Generalization: If the permitted operations were only to toggle a $a\times a$ and $ b\times b$ square where $a, b > c$, then we cannot end up with only a $d \times d$ square turned on for any $ 1\leq d \leq c$. (You can treat $c = 2$ as needed.)

• Even though the board is infinite, since we take finitely many moves to end up with a certain configuration, we may restrict our attention and ignore cells that were not impacted. Henceforth, we are restricted to a $ n ab \times nab$ grid, for some large enough $n$.
  • Actually, it's not relevant that the size is a multiple of $ab$, but I threw that in just in case it was helpful.
  • This pedantic restriction to finiteness is merely to ensure that the sums are finite, which is obvious because only finitely many lights are on.
• We are working mod 2. Toggling the state of a cell can be treated as adding 1 to it's state each time.
  • This simplifies the arithmetic, as we don't have to keep track of which ones are turned on or off.
• To cell $(i,j)$, we assign the weight of $ \alpha^i \times \beta^j$ if the light is on, 0 otherwise. The weight of a certain state is the sum of weights of the individual cells.
• Furthermore, let $ 1 + \alpha + \alpha^2 + \ldots + \alpha^{a-1} = 0 $ and $ 1 + \beta + \beta^2 + \ldots + \beta^{b-1} = 0 $.
  • Note: Treat this as working in $\mathbb{F}_2(\alpha, \beta) / [(1 + \alpha + \alpha^2 + \ldots + \alpha^{a-1}, 1 + \beta + \beta^2 + \ldots + \beta^{b-1} ) ]$, as opposed to substituting in $\alpha, \beta$ as roots of unity.
  • In particular, $ \alpha, \beta$ cannot cancel with each other. Or if $ a = 2k$ is even, then we cannot cancel out $ a^i + a^{i+k} = 0 $ (which could happen if we treated $a^k = - 1$).
• The grid starts out with a sum of weights of 0 (all lights are off).
• Show that toggling a $ a\times a $ (resp $b\times b$) square doesn't change the sum of weights, so we must end up with a weight of 0.
• Show that we can't end up with a single cell turned on, since there is no cell of weight 0.
  • Note: Where does this proof fail for part a of the problem?
• Show that we can't end up with a $ d \times d $ square turned on, since the weight is $ \alpha^I \beta^J ( \sum_{i=1}^d a^i) ( \sum_{j=1}^d b^j) \neq 0$.
• Show that we must have at least $ \min (a, b) $ lights turned on.
  • I suspect that the true minimum is larger, maybe $a+b-1$.