Maths Olympiad Prep

Library / /13 of 17

Combinatorics Difficulty 6.5 National olympiad Prove it Bulgaria

Given is a convex 2024-gon A1A2A2024A_1A_2\dots A_{2024} and 1000 points inside it, so that no three points are collinear. Some pairs of the points are connected with segments so that the interior of the polygon is divided into triangles. Every point is assigned one number among {1,1,2,2}\{1, -1, 2, -2\}, so that the sum of the numbers written in AiA_i and Ai+1012A_{i+1012} is zero for all i=1,2,,1012i = 1, 2, \dots, 1012. Prove that there is a triangle, such that the sum of the numbers in some two of its vertices is zero.
(Emil Kolev)

Solution

Clearly, if there are two adjacent points AiA_i and Ai+1A_{i+1} with opposite numbers, the problem is solved. Without restriction, let A1=1A_1 = 1 and consider all segments AiAi+1A_iA_{i+1} for i=1,2,,1012i = 1, 2, \dots, 1012. Since A1013=1A_{1013} = -1, among the considered segments there is an odd number whose ends are one positive and one negative number. These two numbers can be {1,2}\{-1, 2\} or {1,2}\{1, -2\} and let the number of segments with ends of the first kind be pp and the number of segments with ends of the second species to be qq. Due to symmetry, the number of segments AiAi+1A_iA_{i+1} for i=1013,,2024i = 1013, \dots, 2024 (A2025A1A_{2025} \equiv A_1) with ends {1,2}\{1, -2\} is equal to pp. Therefore, all segments with endpoints {1,2}\{1, -2\} are p+qp+q, which is an odd number.
Now consider any triangle that does not have two vertices with opposite numbers. We have the following possibilities for the three numbers:
(1,1,2),(1,1,2),(1,1,2),(1,1,2),(2,2,1),(2,2,1),(2,2,1),(2,2,1). (1, 1, -2), (1, 1, 2), (-1, -1, 2), (-1, -1, -2), \\ (2, 2, -1), (2, 2, 1), (-2, -2, 1), (-2, -2, -1).
Each of these triangles has an even number (2 or 0) of sides with ends 1 and 2-2. Therefore, the total number of segments with ends 1 and 2-2 (counted in multiples) is an even number. But every line segment inside the 2024-gon is counted twice (once from the two triangles in which it participates), and every line segment that is a side of the 2024-gon is counted once. The resulting contradiction shows that a triangle with the requested property exists. \square

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.