# Why the solution of this brainteaser a linear function?

I have been asked the following brainteaser:

Imagine that you have a grid of dots in 2D placed at regular interval, you draw a convex shape by joining dots. Let us call M the number of dots touching the perimeter of your shape and N the number of dots contained inside the shape but not touching the perimeter.

Can you find a formula function of M and N to compute this surface ?

The solution is a linear function of M and N, do any of you know why this function is linear as it was far from obvious for me that such a problem would be solved by a linear solution ?

(it can be proven that the solution will be linear and then using recursion you can extend this to any value of M and N but that does not give me an intuition of why this would be a linear function)

-
Please look at Pick's Theorem. This does not require convexity. But convexity makes it clearer that we can triangulate. – André Nicolas Jan 30 '13 at 17:24
Are you talking about a two-dimensional grid? If so, I agree on using Pick's Theorem. If not, it may be an interesting question. I don't immediately know if Pick's theorem is readily generalisable. – HSN Jan 30 '13 at 23:51
@HSN, I think it's pretty clear OP is talking 2-D. Pick's Theorem fails in $3$ (and higher) dimensions, as there are lattice solids with small volume and arbitrarily high numbers of lattice boundary points. – Gerry Myerson Jan 31 '13 at 1:09
Yes sorry I was not clear about it being in 2D. I will edit the question. – BlueTrin Jan 31 '13 at 13:19

$$|A|=i+{b\over2}-1$$
here. The surprise consists in the fact that there is such a simple formula, but not in the fact that the number $i$ of interior points and the number $b$ of boundary points enter linearly. Any other exponents would produce wrong results under scaling of $A$ by integer factors.