Skip to main content
OlympiadHQ

Browse · MathNet

Print

Bulgarian Spring Tournament

Bulgaria counting and probability

Problem

Given is a convex 2024-gon 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 , so that the sum of the numbers written in and is zero for all . 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 and with opposite numbers, the problem is solved. Without restriction, let and consider all segments for . Since , among the considered segments there is an odd number whose ends are one positive and one negative number. These two numbers can be or and let the number of segments with ends of the first kind be and the number of segments with ends of the second species to be . Due to symmetry, the number of segments for () with ends is equal to . Therefore, all segments with endpoints are , 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: Each of these triangles has an even number (2 or 0) of sides with ends 1 and . Therefore, the total number of segments with ends 1 and (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.

Techniques

Counting two waysInvariants / monovariantsColoring schemes, extremal argumentsCombinatorial Geometry