# Grid of overlapping squares

I have a grid made up of overlapping $$3\times 3$$ squares like so:

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 ($$3\times 3$$), 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 $$3\times 3$$ . So given point $$(3,2)$$ how can I calculate that there are $$6$$ overlaps at that point?

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.

• 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.