The line connecting two points A(n,0) and B(0,n) has a simple equation,
Superimpose an integer grid on the diagram. The question is about the number of grid points that lie inside small triangles. Obviously, the two triangles next to the axes contain no grid points in their interiors. Prove that, for n prime, each of the remaining triangles contains exactly the same number of grid points.Solution
An nxn square is randomly tossed onto an integer grid. Prove that it may never cover more than (n +1)2 grid points.Solution
- R.Honsberger, Mathematical Morsels, MAA, 1978
- Pick's Theorem
If n is prime then two numbers i and (n - i) are mutually prime for any i (the condition is both necessary and sufficient for the primality of n.) This means that the fraction
Now note that small triangles have the same base (1/n-th of AB) and the same height. Thus all of them share the same area. Since each of the triangles in question has exactly 3 grid points on its boundary (at its vertices), the conclusion follows immediate from Pick's theorem.
In case all four vertices of the square lie at grid points, the square contains (n-1)2 grid points in its interior and 4n on its perimeter. Which totals exactly (n+1)2 points. In a more general case, the perimeter of the square may only contain fewer than 4n points. Indeed, 1 is the smallest distance between the points on the grid. On a line (perimeter of the square) of length 4n there is simply no room for more than 4n points spaced at least 1 unit apart.
From Pick's theorem, n2 = I - B/2 + 1, where I is the number of grid points in the interior of the square and B is the number of points on its boundary. The total number of points covered by the square is given by I + B: