Problem 1

The line connecting two points A(n,0) and B(0,n) has a simple equation, x + y = n. Therefore, it contains all the points in the form (i, n-i), i an integer. There are n-1 such points between A and B. Connect each one of them with the origin O. The lines divide OAB into n small triangles.

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.

Problem 2

An nxn square is randomly tossed onto an integer grid. Prove that it may never cover more than (n +1)² grid points.

References

1. R.Honsberger, Mathematical Morsels, MAA, 1978

• Pick's Theorem
  • Exercises for the Geoboard
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
  • Applications of 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 i/(n-i) is irreducible or visible (from the origin.) We conclude that, besides the pieces OA and OB that run along the axes, no side of any of the small triangles contains a single grid point.

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.

From Pick's theorem, n² = 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:

I + B = I + B/2 - 1 + B/2 + 1 = n² + B/2 + 1 n² + 4n/2 + 1 = (n + 1)²