25
$\begingroup$

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:

  • Flip over all four tiles in any $2 \times 2$ square
  • Flip over all nine tiles in any $3 \times 3$ square.

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?

$\endgroup$
  • 4
    $\begingroup$ and i / would flip one hundred tiles / and i / would flip one hundred more $\endgroup$ – question_asker Feb 12 '16 at 17:17
13
$\begingroup$

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.

    $\endgroup$
    28
    $\begingroup$

    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.

    $\endgroup$
    • 7
      $\begingroup$ This seems to me to be a partial answer, not a full one. The question also says "If so, how many moves are necessary? If not, how close can we be guaranteed to get?" $\endgroup$ – Peter Taylor Feb 11 '16 at 21:12
    • 1
      $\begingroup$ @PeterTaylor Not sure what you would expect for that. This answer does a pretty job good of saying how certain rows will always behave. $\endgroup$ – jpmc26 Feb 12 '16 at 6:53
    • $\begingroup$ @jpmc26 The other answer completes this one with the answer: we can always get to 2 black squares, not always less. $\endgroup$ – T. Verron Feb 12 '16 at 9:04
    1
    $\begingroup$

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

    $\endgroup$

    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.