The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

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.foo[email protected]. Please do not write to this address regarding general admissions or course queries.