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.

I have a grid made up of overlapping 3x3 squares like so:

Grid

The numbers on the grid indicate the number of overlapping squares. Given that we know the maximum number of overlapping squares (9 at the middle), and the size of the squares (3x3), is there a simple way to calculate the rest of the number of overlaps?

e.g. I know the maximum number of overlaps is 9 at point (2,2) and the square size is 3x3. So given point (3,2) how can I calculate that there are 6 overlaps at that point?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

The maximum number of overlaps is always $k^{2}$ (where $k$ is the small square's side length) (assuming the larger square is always of side length $2k-1$).

The number of overlaps at any other point $(i,j)$ is:

$\min(i,2k-i) \cdot \min(j,2k-j)$

As a pointer towards a proof consider the first row and the first column of the larger square which must always be the sequence $(1,2,\ldots,k,\ldots,2,1)$. Then look at why the other rows and columns are the products of their intersection with the edge row and column.

share|improve this answer
    
Sorry - I have just noticed that I've labelled the grid starting from (1,1) instead of (0,0) as in your question. I've left this as it is because it makes the maths slightly simpler. –  tttppp Sep 16 '10 at 9:46

If you are just considering $3\times 3$ squares then the number of overlapping squares at the $(i,j)$ is the number of $1\times 1$ squares (including itself) which are internal neighbours. i.e. neighbouring squares which are not on the edge.

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.