Maths Olympiad Prep

Library / /15 of 19

Combinatorics Difficulty 8.3 Shortlist Find the answer

Let L L denote the set of all lattice points of the plane (points with integral coordinates). Show that for any three points A,B,C A,B,C of L L there is a fourth point D, D, different from A,B,C, A,B,C, such that the interiors of the segments AD,BD,CD AD,BD,CD contain no points of L. L. Is the statement true if one considers four points of L L instead of three?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let L L denote the set of all lattice points in the plane, i.e., points with integer coordinates (x,y) (x, y) . We want to demonstrate that for any three points A,B, A, B, and C C in L L , there exists a fourth point D D , distinct from A,B, A, B, and C C , such that the interiors of the segments AD,BD, AD, BD, and CD CD contain no points of L L .

### Construction of Point D D

1. **Select Three Points A,B,C A, B, C :**
Suppose A=(x1,y1),B=(x2,y2), A = (x_1, y_1), B = (x_2, y_2), and C=(x3,y3) C = (x_3, y_3) are any three distinct points in the plane, with integer coordinates.

2. Define the Midpoints:
Calculate the midpoints of the segments AB,BC, AB, BC, and CA CA :
MAB=(x1+x22,y1+y22),MBC=(x2+x32,y2+y32),MCA=(x3+x12,y3+y12). M_{AB} = \left( \frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2} \right), \quad M_{BC} = \left( \frac{x_2 + x_3}{2}, \frac{y_2 + y_3}{2} \right), \quad M_{CA} = \left( \frac{x_3 + x_1}{2}, \frac{y_3 + y_1}{2} \right).
Note that these midpoints may have non-integer coordinates unless x1+x2,x2+x3, x_1 + x_2, x_2 + x_3, and x3+x1 x_3 + x_1 (similarly for y y -coordinates) are even.

3. **Construct Point D D :**
Choose D=(x1+x2+x32x4,y1+y2+y32y4) D = (x_1 + x_2 + x_3 - 2x_4, y_1 + y_2 + y_3 - 2y_4) where x4,y4 x_4, y_4 are integers ensuring D D does not overlap A,B, A, B, or C C .

4. **Verify that D D is a Lattice Point:**
Since D D is defined in terms of integer sums and differences, it is clear that D D is also a lattice point.

### Verification

1. **Check the Segments AD,BD, AD, BD, and CD CD :**
For each segment, verify that the midpoints MAD,MBD,MCD{M_{AD}, M_{BD}, M_{CD}} are not lattice points:
- The segments do not include any other lattice points if none of these midpoints are lattice.

2. Generalize the Argument:
- It is always possible to choose D D is such a way given that one can always find appropriate x4 x_4 and y4 y_4 (by symmetry and solving congruences modulo 2).

### Extension to Four Points

If you consider four lattice points instead A,B,C, A, B, C, and E E , the task is to find a new point D D that satisfies the same condition. This is inherently more complex as you would attempt to construct D D ensuring no lattice point appears in the interior of segments formed with any of the chosen four points.

In conclusion:
- The statement is true for any three points, as demonstrated, and construction shows that choosing D D as described avoids internal lattice points on segments.
- Extending this to four points requires careful selection of D D as methods from combinatorial and geometric constraints regarding lattice interior segments are more rigorous.

Final statement:
Yes \boxed{\text{Yes}}
The statement about three points is valid, and a similar property can hold under careful construction for four points in more complex arrangements.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.