## Puzzles: solution to problem 2

How many squares (of any size) are there in an 8 by 8 chessboard? What about an 8000 by 8000 chessboard?

Unfortunately this problem has not been formulated correctly. Oh well. If you try to solve it as stated, the answer is obvious: uncountable infinity, even for a 1 by 1 board. Clearly what should have been said is that we are looking for square shapes that cover completely the little black and white squares of the chess board. In other words, if you place the board on Cartesian coordinates in such a way that if the left bottom corner coincides with the origin of your coordinates and space is scaled so that the vertices of the little squares of the board fall on points with integer coordinates, the question is how many squares of integer side length there are with vertices having integer coordinates and with sides parallel to the axes.

Quite a mouthful all that.

Once we know what it is we are looking for, let us see. If the board is a 1 by 1 one, there is only one square, of side 1. If the board is $2 \times 2$, there are 5 squares, one of side 2 and 4 of side 1. So the MSfMC is 3, where I have just invented the concept of “minimal size for maximal complexity”. In a $3\times 3$ board there clearly are 9 squares of side length 1 and 1 square of side length 3. But how many are there of side length 2? To get such a square, you need to count 2 on the x-axis, starting either from 0 or from 1: so there are two ways to lay the projection of your intended square onto the x-axis. Similarly, there are 2 ways to project an $2 \times 2$ square onto the y-axis. Hence there are 4 $2\times2$ squares: their left lower vertices are at $(0,0)$, $(0,1)$, $(1,0)$ and $(1,1)$. So all together there are $9+4+1=14$ squares. But this argument works for chess boards of any size and squares of any size. For example, think about projecting a $6 \times 6$ square contained in an $8 \times 8$ board onto the x-axis. It can fall on one of the intervals $[0,6]$, $[1,7]$, $[2,8]$. So there are 9 such squares, $(8-6+1)^2$. Continuing this train of thought, we see that in an $8 \times 8$ board there are

$(8-1+1)^2+(8-2+1)^2+ \cdots + (8-8+1)^2 =1^2+2^2+\cdots + 8^2=204$

squares. Once the idea is clear, it is easy to prove that an $n \times n$ board contains $\displaystyle\sum_{k=1}^n k^2$ squares. So if you want to work out the answer for $n=800$, you should either prove (by induction) that

$\displaystyle\sum_{k=1}^n k^2 = \displaystyle\frac{1}{6}[2n^3+3n^2+n]$

and then plug in $n=800$, or let MAPLE do the work for you:

sum(k^2,k=1..800);

170986800.

Note that the problem can be easily made harder (!): How many squares are there in an $8 \times 8$ board having vertices at points with integer coordinates and having integer length side (i.e. removing the conditions that the little squares are to be covered completely and that the sides have to be parallel to the axes)? For an $8 \times 8$ board one can count all such squares, but for an $800 \times 800$ one the problem looks challenging to say the least.

(MG)