Serbian Mathematical Olympiad

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

Upper bound. We prove $C \le \frac{15}{4}$. The condition states that in our complete graph there exist both $6$-vertex subsets where the sum of edge weights is positive, and $6$-vertex subsets where it's negative. Therefore, there must exist two $6$-vertex subsets differing by exactly one vertex, such that one has positive sum and the other negative. Indeed, start with a positive $6$-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 $7$-vertex set $S$ - the union of this pair. Examine all seven $6$-vertex subsets obtained by removing one vertex from $S$. Suppose $k$ of them have negative sums (obtained by removing vertices $A_1, \dots, A_k$, called A-vertices), and $7-k$ have positive sums (obtained by removing vertices $B_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 $S$ by replacing:
- All AA-edge weights with their average $x$
- All AB-edge weights with their average $y$
- All BB-edge weights with their average $z$

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

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

We analyze cases based on $k$:

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

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

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

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

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

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