$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}.$
-
- 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)?
- Four points on a Cartesian grid form a square of area
-
How many squares with sides parallel to the grid can be built?
-
For a given
$k \le n,$how many sub-grids of$k\times k$points are there? -
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? -
How can we incorporate that for all values of
$k?$ -
… 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?
-
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{aligned} 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{aligned} $$where we made the change of variable$j=n-k+1.$