Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
3  
and i / would flip one hundred tiles / and i / would flip one hundred more – question_asker Feb 12 at 17:17
up vote 11 down vote accepted

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.

    share|improve this answer

    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.

    share|improve this answer
    7  
    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?" – Peter Taylor Feb 11 at 21:12
    1  
    @PeterTaylor Not sure what you would expect for that. This answer does a pretty job good of saying how certain rows will always behave. – jpmc26 Feb 12 at 6:53
        
    @jpmc26 The other answer completes this one with the answer: we can always get to 2 black squares, not always less. – T. Verron Feb 12 at 9:04

    Your Answer

     
    discard

    By posting your answer, you agree to the privacy policy and terms of service.

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