Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
Count the possible locations of the top left vertex of the $3\times 3$ square. –  Daniel Fischer Jun 14 at 18:28

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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