On a plane, 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 . Then for each six marked points, he calculated the sum of the numbers on all segments connecting these points. It turned out that the absolute value of each such sum is not less than , and among such sums there exist both positive and negative sums. Find the greatest possible .
(Г. Р. Челноков)
Solution
Consider a graph whose vertices are the marked points and edges are the drawn segments.
Upper bound. We prove . The condition states that in our complete graph there exist both -vertex subsets where the sum of edge weights is positive, and -vertex subsets where it's negative. Therefore, there must exist two -vertex subsets differing by exactly one vertex, such that one has positive sum and the other negative. Indeed, start with a positive -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 -vertex set - the union of this pair. Examine all seven -vertex subsets obtained by removing one vertex from . Suppose of them have negative sums (obtained by removing vertices , called A-vertices), and have positive sums (obtained by removing vertices , 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 by replacing:
- All AA-edge weights with their average
- All AB-edge weights with their average
- All BB-edge weights with their average
Clearly since original weights were in .
Lemma. The subgraph with modified weights satisfies the condition with the same constant .
Proof. For any edge type, the number of -vertex subsets containing both its endpoints is constant. Similarly, each -vertex subset contains a fixed number of edges of each type. Therefore:
- The sum in any A--vertex subset is the average of original negative sums, so
- The sum in any B--vertex subset is the average of original positive sums, so
We analyze cases based on :
*Case :* One A-vertex, six B-vertices. The inequalities are:
(A--vertex subset)
(B--vertex subset)
Eliminating gives
*Case :* Two A-vertices, five B-vertices. Inequalities:
(A--vertex)
(B--vertex)
Eliminating gives
*Case :* Three A-vertices, four B-vertices. Inequalities:
(A--vertex)
(B--vertex)
Eliminating gives
Cases reduce to by symmetry (multiplying all weights by ). Thus is proved.
Construction. For any number of A-vertices from to (and remaining as B-vertices), set:
- All BB-edge weights to
- All other edge weights to
Then any -vertex subset with B-vertices has sum , while others have sum .