Maths Olympiad Prep

Library / /86 of 87

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Russia

On a plane, 10610^6 points are marked no three of which are collinear; and all segments between these points are drawn. On each drawn segment Grisha placed a real number whose absolute value does not exceed 11. Then for each six marked points, he calculated the sum of the numbers on all 1515 segments connecting these points. It turned out that the absolute value of each such sum is not less than CC, and among such sums there exist both positive and negative sums. Find the greatest possible CC.
(Г. Р. Челноков)

Solution

Consider a graph whose vertices are the marked points and edges are the drawn segments.

Upper bound. We prove C154C \le \frac{15}{4}. The condition states that in our complete graph there exist both 66-vertex subsets where the sum of edge weights is positive, and 66-vertex subsets where it's negative. Therefore, there must exist two 66-vertex subsets differing by exactly one vertex, such that one has positive sum and the other negative. Indeed, start with a positive 66-vertex subset and transform it into a negative one by changing vertices one at a time - at some step the sign flips, giving the required pair.

Now consider the complete subgraph on a 77-vertex set SS - the union of this pair. Examine all seven 66-vertex subsets obtained by removing one vertex from SS. Suppose kk of them have negative sums (obtained by removing vertices A1,,AkA_1, \dots, A_k, called A-vertices), and 7k7-k have positive sums (obtained by removing vertices B1,,B7kB_1, \dots, B_{7-k}, called B-vertices). We classify edges as:
- AA-edges between two A-vertices
- BB-edges between two B-vertices
- AB-edges between an A-vertex and B-vertex

We modify the edge weights on SS by replacing:
- All AA-edge weights with their average xx
- All AB-edge weights with their average yy
- All BB-edge weights with their average zz

Clearly x,y,z1|x|, |y|, |z| \le 1 since original weights were in [1,1][-1, 1].

Lemma. The subgraph SS with modified weights satisfies the condition with the same constant CC.
Proof. For any edge type, the number of 66-vertex subsets containing both its endpoints is constant. Similarly, each 66-vertex subset contains a fixed number of edges of each type. Therefore:
- The sum ΣA\Sigma_A in any A-66-vertex subset is the average of original negative sums, so ΣAC\Sigma_A \le -C
- The sum ΣB\Sigma_B in any B-66-vertex subset is the average of original positive sums, so ΣBC\Sigma_B \ge C

We analyze cases based on kk:

*Case k=1k = 1:* One A-vertex, six B-vertices. The inequalities are:
15zC15z \le -C
(A-66-vertex subset)
5y+10zC5y + 10z \ge C
(B-66-vertex subset)
Eliminating zz gives 15y5CC315y \ge 5C \Rightarrow C \le 3

*Case k=2k = 2:* Two A-vertices, five B-vertices. Inequalities:
5y+10zC5y + 10z \le -C
(A-66-vertex)
x+8y+6zCx + 8y + 6z \ge C
(B-66-vertex)
Eliminating zz gives 8C5x+25y30C1548C \le 5x + 25y \le 30 \Rightarrow C \le \frac{15}{4}

*Case k=3k = 3:* Three A-vertices, four B-vertices. Inequalities:
x+8y+6zCx + 8y + 6z \le -C
(A-66-vertex)
3x+9y+3zC3x + 9y + 3z \ge C
(B-66-vertex)
Eliminating yy gives 17C15x30z45C4517<15417C \le 15x - 30z \le 45 \Rightarrow C \le \frac{45}{17} < \frac{15}{4}

Cases k4k \ge 4 reduce to k3k \le 3 by symmetry (multiplying all weights by 1-1). Thus C154C \le \frac{15}{4} is proved.

Construction. For any number of A-vertices from 22 to 999,995999,995 (and remaining as B-vertices), set:
- All BB-edge weights to 78-\frac{7}{8}
- All other edge weights to 11

Then any 66-vertex subset with 5\ge 5 B-vertices has sum 154\le -\frac{15}{4}, while others have sum 154\ge \frac{15}{4}.

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.