1
$\begingroup$

Problem: On a 8x8 chessboard all squares are the color white, except for one square (which is black). Show that you can't get to the situation that all squares are white by only recoloring whole rows and columns (recoloring means that in this case that you turn all white squares into black ones and vice versa)

My solution: At the start we have that 63 squares are white and 1 is black. Suppose that you have a column $v$ row which $k$ has times black $v$ white and you recolor this, then the following happens to the total amount of black/white squares on the board:

  1. To the tot. amount of black squares: $-k + (8-k) =8-2k$
  2. To the tot. amount of white squares: $-(8-k) + k =-8+2k$

Note that every such coloring operation thus always results in the addition/substraction of an even number. Since we start with an odd number of black squares, this means that the total amount of black squares will always remain odd (odd + even + ... + even=odd)

Now, suppose that we can get to the situation that all squares are white, then the total amount of black squares is even (since it's 0), but this contradicts the finding that the number of black squares is always odd. Conclusion: you can't get to that situation

Is my solution correct?

$\endgroup$
2
  • 4
    $\begingroup$ Yep, it's a perfectly valid solution - good one :) $\endgroup$ Jul 13, 2020 at 10:40
  • 4
    $\begingroup$ Looks fine to me. Note that you seem to be relying on the fact that the board is of an even size. This is not necessary, as the proof works just as well if you look at just a 2x2 subset of the board that contains the initial black square. Therefore it is true for all boards 2x2 or larger. $\endgroup$ Jul 13, 2020 at 10:41

1 Answer 1

1
$\begingroup$

Your solution seems to be fine for any boards of size $2m\times 2n$.

More general solution (for boards $m\times n$, $m,n>1$) is just proposition of solving such puzzle.

  1. Note, that double-recolouring of any row/column could be considered as neutral operator, so there's no point in doing this.
  2. Row with black tile have to be rocoloured, but then we have a row with single white tile
  3. All columns that have black tiles have to be recoloured, but then we have a board with black tiles everywhere except one row and one column, so
  4. All rows which are not totally white have to be recoloured (note, that now we have done recolorization on ALL possible rows, so no rows recolorozation moves left) - we have board with white tiles except one column, which have black tiles except one, so...
  5. We recolour this column (and use the last possible column recolorization move) - we've finished, where we've started - board with single black tile and no more moves to use.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .