Find the number of squares with all vertices in $\{(x,y) | x, y \in \{1, 2, \ldots, 10\}\}$.

Question

Find the number of squares with all vertices in $\{(x,y) | x, y \in \{1, 2, \ldots, 10\}\}$.

Using a brute-force algorithm, which checks for every four distinct points in this set if they form a square, I've got 825. But I can't find any mathematical proof for this.

I've tried to count them as clear as possible. For each point (from $(1, 10)$, $(1, 9)$, ..., to $(10, 1)$) (most high vertex) I iterate through all the points with less or equal $x$ and less $y$ (most left vertex) and see if the other two points of the square are in the given set.

I can't find any formula or something for counting the squares easier. Can you help me, please? Thanks!

Answer 1

You can classify the squares by the length and orientation of one side. A square where one side is horizontal and of length $4$ can be located with its lower corner in columns $1$ through $6$ and in rows $1$ through $6$ so there are $(10-4)^2=6^2=36$ of them. A square where one side goes three units horizontal and one unit vertical also occupies a $4 \times 4$ square, so there are $36$ of those as well.

If the side goes $a$ units horizontal and $b$ units vertical there are $(10-a-b)^2$ squares so you want $$\sum_{a=1}^9\sum_{b=0}^{9-a}(10-a-b)^2=825$$

Answer 2

Beginning of a Hint...

Define $S_n$ to be the number of squares with all vertices in $Q_n =\{(x,y) | x, y \in \{1, 2, \ldots, n\}\}$.

Then $S_2=1$ and $S_{n+1} = S_n+s_n$ where $s_n$ is the number of squares having at least one vertices with a coordinate equal to $n+1$.