Maths Olympiad Prep

Track / Stage 6 / 220 of 400 #1700 of 2444

Problem 1700

National Olympiad, first round
Combinatorics Difficulty 6.5 Prove it Bulgarian Spring Tournament · 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)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.