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)
We are talking about Pick's area formula
$$|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.
Here is a proof of Pick's formula (there are dozens of them in the literature):
http://www.math.ethz.ch/~blatter/Pick.pdf