One hundred tiles are arranged in a $10 \times 10$ square. Each tile is black on one side and white on the other side. Two types of move are allowed:
Is it always possible, given any starting configuration and using only these actions, to turn every tile white side up? If so, how many moves are necessary? If not, how close can we be guaranteed to get?
Label the tiles like chessboard notation, so that the bottom left is a1 and the top right is j10. Moves will be denoted by referring to a pair of opposite corners in the square being flipped.
If any square not on the j file or the 1st rank is black, we can make it white by flipping the 2x2 square with it at the top left corner (e.g. if a9 is black, flip a9-b8). This can be repeated until all squares except the j file and the 1st rank are white.
Now if a1 is black, we can make it white with this sequence of moves:
a1-c3 b1-d3 a2-b3 b2-c3 c2-d3
This flips a1 and d1 and leaves everything else the same. We can eliminate b1, c1, ... g1 and j10, j9, ... j4 by making a similar series of moves, so we only have to worry about five squares: h1, i1, j1, j2, and j3.
If more than two of these squares are black, we can flip all five with h1-j3 and h2-i3 to reduce the number of black squares.
This guarantees that it is always possible to get down to
two
black squares.
To prove that it is not always possible to reduce the number of black squares further:
Consider these three sets of cells:
Ranks 1, 2, 4, 5, 7, 8, and 10 Ranks 1, 3, 4, 6, 7, 9, and 10 Files b, c, e, f, h, and i
As in @Gamow's answer, each one of these sets has the property that any move flips an even number of tiles in that set, so the parity of the number of black cells in each set cannot change.
Suppose the initial position has two black squares, one on i1 and one on j1. Then the first two sets will always have an even number of black tiles, and the third will always have an odd number. A position with zero black tiles will have an even number in the third set, while a position with one black tile will have an odd number in at least one of the first two sets. Neither of these is possible, so there will always be at least two black tiles.
Answer:
No, this is not always possible.
Argument:
Consider the $70$ cells in the seven rows $1,2$ and $4,5$ and $7,8$ and $10$.
Let us call these cells special.
============
Every $2\times2$-move flips an even number ($2$ or $4$) of these special cells.
============
Every $3\times3$-move flips an even number (always $6$) of these special cells.
============
Suppose that in the initial coloring, an odd number of special cells is white. As the flips do not change the parity of the number of white special cells, it is impossible to reach the all white coloring.
Not to contradict Gamow's parity argument, but to add a different one.
Call a tile "special" iff it's in an even-numbered row. Then each $2\times 2$ flip flips as many special tiles as non-special, and each $3\times 3$ flip flips either $3$ more, or $3$ fewer, special than non-special. Thus the difference $d$ between the number of flipped special tiles and flipped non-special tiles is a multiple of $3$. So a desired pattern is not reachable if it entails $d$ being not a multiple of $3$.
