Maths Olympiad Prep

Library / /3 of 3

Combinatorics Difficulty 6.6 National olympiad Prove it Bulgaria

All points in the plane having integer coordinates are colored in three colors. Find the least positive integer SS having the following property: for arbitrary such covering there exists a triangle of area SS having all its vertices in one and the same color.

Solution

Consider the following two colorings:

(1) Point (x,y)(x, y) is in color ii, 1i21-i-2 if and only if xi(mod2)x \equiv i \pmod{2}.

(2) Point (x,y)(x, y) is in color ii, 1i31 - i - 3 if and only if xi(mod3)x \equiv i \pmod{3}.

It is clear that if SS exists then 2S2S is an integer. Coloring (1) implies that SS could be 11, 22, 33 or greater and coloring (2) shows that SS could be 3/23/2, 33 or greater. Therefore if SS exists then S3S \ge 3.

We prove that for arbitrary coloring there exists a triangle of area 33 having all its vertices in one and the same color. Note that for some d{1,2,3}d \in \{1, 2, 3\} there exist points A=(x,y)A = (x, y) and B=(x+d,y)B = (x+d, y) of the same color. Indeed, it suffices to consider the points (0,0),(1,0),(2,0),(3,0)(0,0), (1,0), (2,0), (3,0). If mABm \equiv AB and ll is parallel to mm at distance 6d\frac{6}{d} from mm then the line lOxl \parallel Ox is either having points of only two colors or we have a triangle of area 33.

We say that a color cc permits distance aa in the line ll if there exist two points on ll having color cc and at distance aa apart.

If there exists a distance a{1,2,3,6}a \in \{1, 2, 3, 6\} that is permitted by the two colors on ll then the line plp \parallel l at a distance 6a\frac{6}{a} from ll is having all its points in the same color. If such a distance does not exist then one of the colors ll permits all distances in the set {2,3,6}\{2, 3, 6\}.

(Indeed, assume that color c1c_1 does not permit distance 11, and there exists at least one point P0P_0 from ll having color c1c_1. Two neighbors of P0P_0 - points P1P_{-1} and P1P_1 are colored in c2c_2, so c2c_2 permits distance 22. Therefore c1c_1 does not permit distance 22 and points P2P_{-2} and P2P_2 are of color c2c_2. As above c2c_2 does not permit distance 33. c1c_1 does not permit distance 33 and P3P_{-3} and P3P_3 are of color c2c_2. Thus c2c_2 permits all distances in {2,3,6}\{2, 3, 6\}.)

In both cases there exists a line pOxp \parallel Ox and color cc from pp that permits all distances in the set {2,3,6}\{2, 3, 6\}.

Consider the lines u1,u2,u3u_1, u_2, u_3, parallel to pp and such that uiu_i, i=1,2,3i = 1, 2, 3 is at distance ii above pp. It follows from the above that all such lines are having points only in two colors. Finally, consider all nine points of intersection of lines u1,u2,u3u_1, u_2, u_3 with lines x=0x = 0, x=3x = 3, x=6x = 6. It is easy to see that there exists a triangle of area 33 having all its vertices colored in the same color.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.