2
$\begingroup$

We have a matrix made up of $m$ by $n$ dots. Can you give a function that counts the number of squares that can be found by joining any $4$ dots in it?

$\endgroup$
1
  • $\begingroup$ I thought this Q must be an old one, but I couldn't find it. $\endgroup$ Oct 28, 2015 at 15:34

1 Answer 1

1
$\begingroup$

For every $m\ge n$ (otherwise just swap $m$ and $n$) the number of squares $N$ is:

$N=\sum_{i=1}^{n-1}(n-i)\times(m-i)\times i$

Where $(n-i)\times(m-i)$ counts all squares of sidelength $i$ and sides parallel to the rows and columns and multiplies it by the amount of squares we get when we slide their corners along those sides($\times i$).

Example: squares size 3 in a 5 by 5 matrix:

++++*  *++++
+**+*  *+**+
+**+*  *+**+
++++*  *++++
*****  *****

*****  *****
++++*  *++++
+**+*  *+**+
+**+*  *+**+
++++*  *++++

squares by sliding along the edges of one size 3 square:

++++
+**+
+**+
++++

*+**
*+++
+++*
**+*

**+*
+++*
*+++
*+**

(i know its ugly but i couldn't do better)

$\endgroup$
2
  • $\begingroup$ This formula is easy. The trick is counting all possible tilted squares as well. $\endgroup$ Oct 28, 2015 at 17:15
  • $\begingroup$ @ghosts_in_the_code: This formula does that. I think better diagrams might be needed to explain why though ... $\endgroup$ Oct 28, 2015 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.