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$
  • $\begingroup$ I thought this Q must be an old one, but I couldn't find it. $\endgroup$ – ghosts_in_the_code Oct 28 '15 at 15:34
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)

| improve this answer | |
$\endgroup$
  • $\begingroup$ This formula is easy. The trick is counting all possible tilted squares as well. $\endgroup$ – ghosts_in_the_code Oct 28 '15 at 17:15
  • $\begingroup$ @ghosts_in_the_code: This formula does that. I think better diagrams might be needed to explain why though ... $\endgroup$ – Tyler Seacrest Oct 28 '15 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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