If 5 points are placed in the plane at lattice points (i.e. points where and are both integers) such that no three are collinear, then there are 10 triangles whose vertices are among these points. What is the minimum possible number of these triangles that have area greater than ?
Solution
By the pigeonhole principle, the 5 points cannot all be distinct modulo 2, so two of them must have a midpoint that is also a lattice point. This midpoint is not one of the 5 since no 3 are collinear. Pick's theorem states that the area of a polygon whose vertices are lattice points is where is the number of lattice points on the boundary and is the number in the interior. Thus those two points form the base of 3 triangles whose area will be greater than by Pick's theorem since there are 4 lattice points on the boundary. Now it also turns out that at least one of the triangles must contain a lattice point, thus giving us a fourth triangle with area greater than . This is actually pretty easy to show with the aid of a picture or some visualization. Suppose we have 4 points and we're trying to find a 5th one so that no triangle will contain an interior lattice point. The 4 lattice points must form a quadrilateral of area 1, so in fact it is a parallelogram (think deeply about it). Draw the four sides, extending them throughout the plain. Each vertex is now the tip of an infinite triangular region of the plane, and if the 5th lattice point is chosen in that region then the triangle formed by the 5th point and the two vertices of the parallelogram adjacent to the one we are considering will form a triangle containing the vertex we are considering. But the part of the plane that isn't in one of these 4 regions contains no lattice points or else we could draw a parallelogram congruent to the first one with lattice point vertices and containing that lattice point, but that would violate Pick's theorem since the parallelogram has area 1. Therefore we must have a fourth triangle with area greater than (one must justify that this really is in addition to the 3 triangles we already knew we'd get). An example that achieves this minimum is the points , and . Therefore the minimum possible number of these triangles that have area greater than is 4. A less trivial example that achieves the minimum is , and .