# 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}.$$

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

## Warm-up Questions

1. 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?
2. Could you have a tilted square of area $$100$$ (in grid area units) with vertices on the grid?
3. Simplify $$\sum_{k=0}^{n}k(n-k).$$
4. 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 1
How many squares with sides parallel to the grid can be built?
• Hint 2
For a given $$k \le n,$$ how many sub-grids of $$k\times k$$ points are there?
• Hint 3
For 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 4
How 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.tasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.