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?

My 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?


Yes, it is!

Since you always have to color one unprviously colored unti square, and aince there are $100$ unti 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 unti 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 unti 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 unti 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 intoduce 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 unti 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 unti sqaures, 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$.

  • $\begingroup$ I don't get it, why does that mean it is a maximal number of move? $\endgroup$ – Maria Mazur Feb 6 '18 at 21:15
  • 2
    $\begingroup$ You're talking about about 4 adjacent cells, but the OP is not, as is clear from his algorithm. He's talking about the four cells at the corners of a sub-rectangle. $\endgroup$ – saulspatz Feb 6 '18 at 21:17
  • $\begingroup$ @saulspatz Thanks! I did indeed misunderstand ... I changed my answer accordingly. $\endgroup$ – Bram28 Feb 7 '18 at 1:45

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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.