1
$\begingroup$

Squares Problem

I am trying to find a proof for the general case of the solution to the 'Squares' Problem.

This is what I have managed to figure out: If n is the number of squares in the top row, then the number of 3-by-3 squares is given by the formula $(n-2)^2$ I know this works for $n=4$ (the case in the diagram), because there are four 3-by-3 squares. It also works for $n=5$ and $n=6$, because I have drawn the cases and counted the 3-by-3 squares.

I know empirical evidence such as this does not constitute proof, so my answer to the $n=60$ case, that there are $58^2$ 3-by-3 squares remains unproven.

I have used the induction tag only because I tried (and failed) to use this method this afternoon, I will be happy with any kind of proof.

$\endgroup$
  • 4
    $\begingroup$ Count the possible locations of the top left vertex of the $3\times 3$ square. $\endgroup$ – Daniel Fischer Jun 14 '14 at 18:28
2
$\begingroup$

To make a $3 \times 3$ square you must chose three consecutive rows and three consecutive columns. How many ways are there to make such a choice? Well there are $n-2$ ways to choose the rows and $n-2$ ways to choose the columns in an $n \times n$ square. Thus your $(n-2)^2$ is the correct count, and this is the reason why.

$\endgroup$
4
$\begingroup$

You can note that the central square of the $3\times3$ square set can correspond to any square of the $n\times n$ square set, with the exception of those on the borders. This directly leads to the solution $(n-2)^2$ that you found.

$\endgroup$

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.