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 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)

share|improve this question
3  
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
1  
@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

1 Answer 1

up vote 2 down vote accepted

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

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.