What is the largest possible number of moves that can be taken to color the whole grid?

Question

Consider a $10\times 10$ grid. On every move, we color $4$ unit squares that lie in the intersection of some two rows and two columns. A move is allowed if at least one of the $4$ squares is previously uncolored. What is the largest possible number of moves that can be taken to color the whole grid?

---

Attempt: It is easy to get $81$ moves: By always choosing the first line, the first column and a square of the remaining $9\times 9$ grid as the lower right square, the whole grid can be colored in $81$ moves. But is this a maximum number of moves?

Answer 1

Yes, it is!

Since you always have to color one unpreviously colored unit square, and since there are $100$ unit squares, the maximum is $100$ ... but of course you won't be able to do $100$, since on the first move you are immediately coloring $4$ new unit squares instead of just one new one. That is, you 'lose' $3$ moves with respect to the imaginary 'perfect' schedule of moves that would color exactly one new unit.

Now, as you go along making moves, we can show that you are going to have to 'lose' at least $16$ more moves with respect to that 'perfect' schedule, and that is because for each previously unused row or column that you will be using for the first time (and clearly you will have to use each of the rows and columns at some point), you 'lose' $1$ move.

For example, suppose your first move is by using rows $1$ and $2$ and also columns $1$ and $2$, and for your second move you use rows $1$ and $2$ and columns $1$ and $3$. So now you use column $3$ for the first time, and since you end up coloring two previously uncolored unit squares, you do indeed 'lose' $1$ move with respect to the 'perfect $100$'.

Notice that this holds true in general. If a new move uses a single row or column for the first time, then obviously you end up coloring two new unit squares instead of just one new one, and thus lose one move.

Of course, you could also use two new rows or columns during a move. E.g. maybe the second move was still using columns one and two, but now you select rows three and four. But notice that now you end up coloring four new unit squares, and thus incur a loss of three ... so now you get even further 'behind' ... indeed, going about it this way is a good way to minimize the number of moves, not maximize them.

OK, but we can also introduce one new column and one new row, e.g. move two uses columns $1$ and $3$, as well as rows $1$ and $3$. Well, notice that you end up coloring three new unit squares, and thus incur a loss of $2$, which is exactly the number of new rows and columns you are introducing, so this isn't helping either.

Similarly, if we introduce two new rows and one new column, we are coloring four new unit cells, for a loss of $3$, whch again equals the number of new rows and columns.

OK, so the only interesting move left would be when you introduce two new columns and two new rows, e.g. When move two would be using rows and columns $3$ and $4$. This time, we are again coloring four new unit squares, thus incurring a loss of $3$, but we introduced four new rows and columns, and so we seem to beat the dreadful 'every new use of row or column incurs a loss of $1$' rule. Unfortunately, this kind of move isn't going to help you either, since anytime you do introduce two new rows and two new columns at the same time in one move, it then becomes impossible to fill up all the squares for all those rows and columns introduced at that time without incurring at least one further loss of $1$, and that is because in order to do that there has to be a first timewhere you combine an 'old' row or column with one of the newly introduced row or column for the first time, at which point you are forced to color at least two new unit squares, incurring that loss of $1$. Therefore, even if you introduce two new rows and two new columns at the same time, you will incur a loss of at least $4$ after all.

So, since after making that first move, there will be $8$ unused columns, and also $8$ unused rows, you are forced to take a 'loss' of at least $16$, and since you already lost $3$ on the first move, the minimal loss is $19$, meaning that the maximum number of moves is indeed $100-19=81$.

Answer 2

For $n>=2$ at most $(n-1)^2$ moves are possible. This is clear when $n=2,$ so suppose $n>2$ and the theorem is true for $n-1$. Now moves that involve neither the last row nor the last column color cells in the $(n-1)\times(n-1)$ square in the upper left-hand corner, so there are most $(n-2)^2=n^2-4n+4$ such moves, by the induction hypothesis.

We now have to color the remaining $2n-1$ cells in the last row and last column. There can be no more than $2n-1$ additional moves, but the first move involving the last row colors two cells in that row, and the the first move involving two cells in the last column colors two cells in that column, so we have at most $2n-3$ additional moves, for a total of $n^2-2n+1=(n-1)^2.$ (If we attempt to save a move by coloring the lower right-hand corner first, this move colors three uncolored cells, so we lose both cells at once.)

Answer 3

We can think of this table as a matrix $M$ filled with nonegative numbers. If the cell is colored it has number $>0$ and if it is not it has $0$. So, at the start we have $M= 0$. Now in any moment of process, if we want to color $4$ entries marked with $*$ say $$M= \begin{bmatrix} & \vdots & & \vdots & \\ \cdots & * & \cdots & * & \cdots \\ & \vdots & & \vdots & \\ \cdots & * & \cdots & * & \cdots\\ &\vdots & &\vdots & \\ \end{bmatrix} $$ then at least one $*$ is $0$, so we can color those cells or equivalently we can add to $M$ matrix: $$E= \begin{bmatrix} & \vdots & & \vdots & \\ \cdots & 1 & \cdots & 1 & \cdots \\ & \vdots & & \vdots & \\ \cdots & 1 & \cdots & 1 & \cdots\\ &\vdots & &\vdots & \\ \end{bmatrix} $$ which has exactly four $1$ and all other entries $0$. The process ends when there is no $0$ entry.

Now observe $81$ special matrix of form as $E$ is, which has first $1$ in down left corner, second $1$ in first colum in $i$-th row ($i>1$), third $1$ in first row in $j$-th column $j>1$ and fourth $1$ in $i$-th row and $j$-th column. Mark this special matrix with $S_{i,j}$.

Clearly, in whole process we can add each matrix of type $E$ at most once and in particulary any special matrix at most once.

Also, if we add to $M$ any matrix of form as $E$ is (but it is not special), with wich we want to color $k$ uncolored cells in green area, (so $1\leq k\leq 4$) we can substitute this $E$ with $k$ special matrices. So we can consider this process as adding only special matrices to $M$, but this we can not do more than $81$ times and we are done.