Maths Olympiad Prep

Library / /17 of 23

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(r1−1)+y1(y1−1)+g1(g1−1)≥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+g12≥56r_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,g1≤5r_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+g12≥56r_1^2 + y_1^2 + g_1^2 \ge 56 does not hold.
WLOG assume r1≥6r_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.