The Computer Laboratory

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.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.