Maths Olympiad Prep

Library / /28 of 94

Combinatorics Difficulty 5.5 AIME, harder Prove it Hong Kong

There are nn points on the plane, no three of which are collinear. Each pair of points is joined by a red, yellow or green line. For any three points, the sides of the triangle they form consist of exactly two colours. Show that n<13n < 13.

Solution

It suffices to show that the case n=13n = 13 is impossible since we can remove extra points. For the jjth point, let rj,yj,gjr_j, y_j, g_j be the numbers of lines having this point as an endpoint which are in red, yellow, and green respectively.

For any XYZ\triangle XYZ, WLOG assume XYXY and XZXZ are red. Then this triangle corresponds to two red lines from XX, and this correspondence is one-to-one. It follows that the number of triangles is
j=113[(rj2)+(yj2)+(gj2)]. \sum_{j=1}^{13} \left[ \binom{r_j}{2} + \binom{y_j}{2} + \binom{g_j}{2} \right].
But then it is clear that there are (133)=286\binom{13}{3} = 286 triangles. By the pigeonhole principle, WLOG assume
(r12)+(y12)+(g12)28613=22. \binom{r_1}{2} + \binom{y_1}{2} + \binom{g_1}{2} \ge \frac{286}{13} = 22.
This gives r1(r11)+y1(y11)+g1(g11)44r_1(r_1 - 1) + y_1(y_1 - 1) + g_1(g_1 - 1) \ge 44. Since r1+y1+g1=12r_1 + y_1 + g_1 = 12, this implies r12+y12+g1256r_1^2 + y_1^2 + g_1^2 \ge 56.
We claim that one of r1,y1,g1r_1, y_1, g_1 is at least 6. Suppose on the contrary that r1,y1,g15r_1, y_1, g_1 \le 5. As r1+y1+g1=12r_1+y_1+g_1 = 12, it suffices to check (r1,y1,g1)=(5,5,2),(5,4,3),(4,4,4)(r_1, y_1, g_1) = (5, 5, 2), (5, 4, 3), (4, 4, 4). In all cases, r12+y12+g1256r_1^2 + y_1^2 + g_1^2 \ge 56 does not hold.
WLOG assume r16r_1 \ge 6. Suppose AB,AC,AD,AE,AF,AGAB, AC, AD, AE, AF, AG are red. By assumption, none of the lines formed by B,C,D,E,F,GB, C, D, E, F, G is red. Since R(3,3)=6R(3,3) = 6, there must be a yellow or green triangle among these 6 points, contradiction. This proves n<13n < 13.

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.