Let $n$ be a positive integer. Initially, a $2n \times 2n$ grid has $k$ black cells and the rest white cells. The following two operations are allowed : (1) If a $2\times 2$ square has exactly three black cells, the fourth is changed to a black cell; (2) If there are exactly two black cells in a $2 \times 2$ square, the black cells are changed to white and white to black. Find the smallest positive integer $k$ such that for any configuration of the $2n \times 2n$ grid with $k$ black cells, all cells can be black after a finite number of operations.
Problem
Source: 2023 China TST Problem 24
Tags: combinatorics, China TST
02.04.2023 01:25
Doesn’t 4 just work for n>= 2?
02.04.2023 01:32
Yea I agree. The answer is 4 for n>=2 and 3 for n=1 Basically have an L shape, then it can be turned into a 3*2 black grid. Shift the top 2*2 square right, we can create a 3*3 grid, and repeat. To see k=3 doesn't work: either we are never able to add a new square, or we can add a black square then at this moment we must have a 2*2 grid of black cells. The only operations available from (2) is to shift a domino of black cell, so (1) is impossible to apply.
02.04.2023 01:46
Clarification: the problem should be asking for the smallest positive integer $k$ such that for ANY configuration of the $2n \times 2n$ grid with $k$ black cells, all cells can be black.
02.04.2023 02:24
Ok, I think the answer is n^2+n+1. Construction of n^2+n doesn't work: let the top-left to bottom-right diagonal have all black cells. Partition the 2n*2n grid into n^2 2*2 grids. In the 2*2 grids lower than diagonal, we paint the bottom left cell black. In the 2*2 grids higher than diagonal, we paint the top-right cell black. proof that n^2+n+1 always works: Basically, if we ever get a black domino, then we win. Consider the 2*2n strip the domino is in. If there are any other black cells in it, then we can construct a 2*2 black grid, then if any other cells in the grid are black, we can create a 3*2 black grid and win. On the other hand, if there are no black cells in the strip. We can delete this strip and then split the remaining grid into two. And "induct" down. So we only need to show that when there are n^2+n+1 black cells, then we can create a black domino by only using operation (2). EDIT: @below you're right, that was a dumb mistake
02.04.2023 02:59
HaO-R-Zhe wrote: Now, partition the 2n*2n grid into 2*2n horizontal strips. One strip has at least n+2 cells. Within this strip a domino a black cell is able to be created (if it's vertical we win immediately, so we assume the domino is horizontal). Have I misunderstood you? This is a $2\times 2n$ vertical strip with $n=6$ and $8$ black cells where no black domino can be created. xo ox oo xo ox oo xo ox oo xo ox oo
02.04.2023 09:16