What is the minimal number of operations needed to repaint a entirely white grid $100 \times 100$ to be entirely black, if on one move we can choose $99$ cells from any row or column and change their color?
Problem
Source: St. Petersburg 2023 11.4
Tags: combinatorics
starchan
13.08.2023 02:20
nice nice
Switch grid to board, since boards are more natural to think about.
We will show that the minimum number of operations required is $200$. We will treat the operation as choosing a row or column and a cell contained in it, and then flipping everything in chosen structure except the chosen cell. For the sake of brevity, we shall talk about an operation as "touching cell $c$ along row/column". This means everything other than $c$ must be flipped in its row/column.
First let us show that $200$ operations are sufficient. Number the cells $(i, j)$ with fixed $i$ denoting a row and fixed $j$ denoting a column. Touch cells $(1, i)$ along column $i$ for all $1 \leq i \leq 100$. This takes $100$ operations and colors everything black except for column $1$. Now we touch each $(i, 1)$ along column $1$ for $1 \leq i \leq 100$. Then everything in the column gets flipped $100-1 = 99$ (which is odd) times, and the entire board has been painted black.
Now let us show that we require at least $200$ operations. Observe that the number of white squares switches parity every operation and it is initially even and finally even as well. It follows that there are an even number of operations. So it suffices to show that we require at least $199$ operations. We have the key:
Observation: Suppose cells $c_1, c_2$ are in the same row (column). Then touching $c_1, c_2$ along said row (column) produces the same effect as simply flipping $c_1, c_2$ individually.
Suppose touching cells $r_1, r_2, r_3, \dots, r_m$ along rows and cells $c_1, c_2, \dots, c_m$ along columns produces the desired effect. Create a set $\mathcal S$ and repeat the following (as long as we can):
If $r_i, r_j$ are in the same row for distinct $i, j$ then we remove $r_i, r_j$ from the sequence $r_1, r_2, \dots, r_m$ and add them to $\mathcal S$.
If $c_i, c_j$ are in the same column for distinct $i, j$ then we similarily remove $c_i, c_j$ from their sequence and add them to $\mathcal S$.
Note that the sequences $r_i$ and $c_i$ have different lengths (possibly empty) than before and that the total number of operations is now given by $m+n+|\mathcal S|$ now. More importantly, the $r_i$ are acting on different rows and the $c_i$ are acting on different columns. Note also that $|\mathcal S|$ has even size, and it's elements can be paired up into pairs of cells along same rows or columns.
Due to the Observation, it follows that we now touch each $r_i$ along its row, each $c_i$ along its column and flip all cells present in $\mathcal S$ to produce an all black board.
Case 1. $m, n \leq 99$
Consider the $100-m$ rows not passing through any of the $r_i$ and the $100-n$ columns not passing through any of the $c_i$. The $(100-m)(100-n)$ cells formed by their pairwise intersections can only possibly be affected by actions on $\mathcal S$. Since each of them is flipped at least once, it follows that $|\mathcal S| \geq (100-m)(100-n)$. Hence the number of operations is: \[m+n+|\mathcal S| \geq 100^2-99(m+n)+mn = 199+(99-m)(99-n) \geq 199\]as required.
Case 2. One of $m, n$ is $100$ and the other is $\geq 2$.
Without losing generality let us assume $m = 100$. This implies that each row of the board contains exactly one $r_i$. Thus the actions of the $r_i$ flip the entire board except the cells $r_i$ themselves. Imagine considering the operations on the flipped board now. Precisely the cells $r_i$ are black and once the $c_i$s operate exactly $99n$ cells will flip, implying that at least $99n-100$ will turn black. These cells will be forced to be in $\mathcal S$ then, implying that we require at least $100+n+99n-100 = 100n \geq 200$ operations.
Case 3. $m = 100, n = 0$.
In this case, observe that there are $100$ cells left white after the action of the $r_i$ and $c_i$. These have to be in $\mathcal S$, implying that we need at least $m+n+|\mathcal S| = 200$ operations.
Case 4. $m = 100, n = 1$.
This case is impossible since $m+n+|\mathcal S|$ cannot be even, due to $101$ being odd and $|\mathcal S|$ is even.
All in all, we see that we require at least $200$ operations to make the board all black, as desired.