# Practice Paper 2 Question 18

How many squares (including tilted ones) can be built with vertices on a grid of \(n\times n\) points? The following may be useful: \(\sum\limits_{k=1}^n k^2=\frac{n(n+1)(2n+1)}{6}\) and \(\sum\limits_{k=1}^n k^3=\frac{n^2(n+1)^2}{4}.\)

## Related topics

## Warm-up Questions

- Four points on a Cartesian grid form a square of area \(100\) (in grid area units) with sides parallel to the grid. How many points lie on the boundary of this square?
- Could you have a tilted square of area \(100\) (in grid area units) with vertices on the grid?
- Simplify \(\sum_{k=0}^{n}k(n-k).\)
- Three points with coordinates \((1,3),\) \((2,1)\) and \((4,2)\) lie on the perimeter of a square. What is the smallest such square (in terms of area)?

## Hints

- Hint 1How many squares with sides parallel to the grid can be built?
- Hint 2For a given \(k \le n,\) how many sub-grids of \(k\times k\) points are there?
- Hint 3For a given sub-grid of \(k\times k\) points, how many squares with vertices on the outer points of the sub-grid can be built?
- Hint 4How can we incorporate that for all values of \(k?\)
- Hint 5... knowing that there are \((n-k+1)^2\) sub-grids of \(k\times k\) points and \(k-1\) squares (including tilted ones) per each such sub-grid?

## Solution

We can first count the number of different sub-grids of size \(k\times k,\) then count the number of squares with vertices only on the outer points of each sub-grid. This avoids counting duplicates (can you see why?).

The number of sub-grids of size \(k\times k\) is \((n-k+1)^2\) because \(n-k+1\) is the number of possible horizontal (or vertical) shifts of such a sub-grid.

For each \(k\times k\) sub-grid, a square with vertices on the outer points of the sub-grid is uniquely defined by the position of the vertex on one side of the sub-grid. Hence, there are \(k-1\) different such squares.

Finally, the total number of squares is the sum over the sub-grids: \[ \begin{align} N&=\sum_{k=2}^{n} (k-1)(n-k+1)^2 \\ &=\sum_{j=1}^{n-1} (n-j)j^2 \\ &= n \sum_{j=1}^{n-1}j^2 - \sum_{j=1}^{n-1}j^3 \\ &= \frac{n^2(n+1)(2n+1)}{6}-\frac{n^2(n+1)^2}{4} \\ &= \frac{n^4-n^2}{12}, \end{align} \] where we made the change of variable \(j=n-k+1.\)

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.. Please do not write to this address regarding general admissions or course queries. tasc@sulp.ecitcarp