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)