Tuesday, 20 September 2016

Chess Puzzle

To solve the chess problem, my first instinct was to count from the bottom up - so starting with the smallest squares (1 x 1) and going up in size. But trying to figure out the number of 2 x 2 squares seemed daunting. It occurred to me that it made more sense to start from the top down.

Working "down" I noted that there is one 8 x 8 square, four 7 x 7 squares and nine 6 x 6 squares. The pattern that seems to emerge is one of square numbers, which seems to be confirmed by the existence of sixty-four 1 x 1 squares. It seems highly likely that the answer would be:

1 + 4 + 9 + 16 + 25 + 36 + 49 + 64 = 204

or


 which could then be expanded to any size square board by replacing 8 with n.

However, though this solution "feels" right, it isn't an actual proof.


I then thought about approaching it from a different way. When dealing with big problems I usually like to start with smaller ones and see if a pattern can emerge there. So, if we were dealing with a 1x1 square we would have, naturally, 1 square. If it was a 2x2 square, we would have 1 + 4. If it were a 3x3 square, it would be 1 + 4 + 9, and so on. Once again, the formula seems to fit, but this is still not a proof.

I was feeling both sure that I had the answer and yet frustrated that I couldn't find the proof... Then, after leaving the problem for a while and coming back to it, I reframed the question as follows:

If you have an n x n board, how many (n-1) x (n-1) squares will you have?

Well, I thought, any (n-1) x (n-1) square must occupy all but 1 row and 1 column (with one interlocking square) of the n x n square (as in the figure below). These rows and columns must be at the end of the chessboard. Thus, for there to be more than one square, you would need a unique combination of this row and column. Since there are two possibilities for placing each row (the first and last row) and two possibilities for each column (the first and last column), there are 2 x 2 = 4 possible squares.



By the same logic, when you have a (n-2) x (n-2) square, you would have a square that occupies all but two rows and two columns (see the next figure). To consider the number of possibilities, I visualized the square occupying the board and realized that the question could be interpreted as how many rows were on one side of the square (say on top of it). There could be zero, 1, or 2 of the rows. Hence there are 3 possibilities, and the same for the number of columns; thus there are 3 x 3 = 9 possibilities. Having found a logical explanation for why the square numbers come from, I am both more confident in the answer and satisfied with the formula.



This problem can teach a lot of learning skills in mathematical problem solving: breaking big problems into smaller ones, thinking visually, and re-interpreting problems (the number of squares = the number of row-column combinations).

In addition to obvious changes to the problem (such as changing the size of the grid), both the shape of the grid and the pieces searched for can be changed (for example, to 2x3 rectangles, or, if you want to get really tricky, any rectangle). Additional complexities can be added by mutilating the board. How many squares will there be if we remove one of the corners, or if we cut a square shaped hole in the middle of the board? Or even the nature of the question can change: for example, how many squares are there in the board which do not have an edge on the outer border of the chessboard? 

1 comment:

  1. Lovely, Ali! What a thoughtful and interesting blog on solving and using this puzzle.

    ReplyDelete