Maths Olympiad Prep

Library / /63 of 121

Combinatorics Difficulty 6.0 National Olympiad Prove it India

Problem:

All the points with integer coordinates in the xyx y-plane are coloured using three colours, red, blue and green, each colour being used at least once. It is known that the point (0,0)(0,0) is coloured red and the point (0,1)(0,1) is coloured blue. Prove that there exist three points with integer coordinates of distinct colours which form the vertices of a right-angled triangle.

Solution

Solution:

Consider the lattice points (points with integer coordinates) on the lines y=0y=0 and y=1y=1, other than (0,0)(0,0) and (0,1)(0,1). If one of them, say A=(p,1)A=(p, 1), is coloured green, then we have a right-angled triangle with (0,0)(0,0), (0,1)(0,1) and AA as vertices, all having different colours. (See Figures 1 and 2.)

Figure 1

If not, the lattice points on y=0y=0 and y=1y=1 are all red or blue. We consider three different cases.

Case 1. Suppose a point B=(c,0)B=(c, 0) is blue. Consider a green point D=(p,q)D=(p, q) in the plane. Suppose p0p \neq 0. If its projection (p,0)(p, 0) on the xx-axis is red, then (p,q)(p, q), (p,0)(p, 0) and (c,0)(c, 0) are the vertices of a required type of right-angled triangle. If (p,0)(p, 0) is blue, then we can consider the triangle whose vertices are (0,0)(0,0), (p,0)(p, 0) and (p,q)(p, q). If p=0p=0, then the points DD, (0,0)(0,0) and (c,0)(c, 0) will work. (Figure 3.)

Case 2. A point D=(c,1)D=(c, 1), on the line y=1y=1, is red. A similar argument works in this case.

Figure 2

Fig-4

Case 3. Suppose all the lattice points on the line y=0y=0 are red and all on the line y=1y=1 are blue points. Consider a green point E=(p,q)E=(p, q), where q0q \neq 0 and q1q \neq 1. (See Figure 4.) Consider an isosceles right-angled triangle EKME K M with E=90\angle E=90^{\circ} such that the hypotenuse KMK M is a part of the xx-axis. Let EME M intersect y=y= in LL. Then KK is a red point and LL is a blue point. Hence EKLE K L is a desired triangle.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.