Weighted graph problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Weighted graph problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: All Russian 2025 10.4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

210 posts

egxa

#1 h Apr 18, 2025, 9:47 AM

Y by

In the plane, $10^6$ points are marked, no three of which are collinear. All possible segments between them are drawn. Grisha assigned to each drawn segment a real number with absolute value no greater than $1$ . For every group of $6$ marked points, he calculated the sum of the numbers on all $15$ connecting segments. It turned out that the absolute value of each such sum is at least $C$ , and there are both positive and negative such sums. What is the maximum possible value of $C$ ?

This post has been edited 2 times. Last edited by egxa, Apr 21, 2025, 7:22 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

internationalnick123456

134 posts

internationalnick123456

#2 h Apr 21, 2025, 12:42 PM

Y by

Claim. There exists $7$ points such that the sums corr. to $6$ among these points attain both positive and negative values.
Proof. Notice that from any group of $6$ points, we can replace one point at a time with another from the remaining point, and after finitely many steps, we can obtain any group of $6$ points. By continuity, we conclude our claim.
Now, denote the $7$ points as $A_1, A_2, \ldots, A_7$ , and let $S_i$ be the sum corresponding to the subset of $6$ points excluding $A_i$ .
Wlog, assume $S_1, \ldots, S_k > 0$ and $S_{k+1}, \ldots, S_7 < 0$ .
Let $X,Y,Z$ be the sum over all segments $A_iA_j$ with: $1\leq i<j\leq k, 1\leq i\leq k<j\leq 7, k<i<j\leq 7$ , respectively.
Then we have $kC\leq S(A_1)+\cdots +S(A_k)= (k-2)X + (k-1)Y + kZ\quad(1)$ $-(7-k)C\geq S(A_{k+1})+\cdots + S(A_7)=(7-k)X + (6-k)Y + (5-k)Z\quad(2)$
Considering $(7-k)\times (1) - (k-2)\times (2)$ , we get $(7-k)(2k-2)C\leq 5Y + 10Z\leq 5k(7-k)+5(7-k)(6-k)=30(7-k)\Rightarrow C\leq \dfrac{15}{k-1}$ By switching the roles of positive and negative, we also get $C\leq \dfrac{15}{6-k}$
Moreover, considering $(6-k)\times (1) - (k-1)\times (2)$ we have $C(14k-2k^2-7)\leq 5(Z-X)\leq 5(21-7k + k^2)$ .
If $k\leq 2$ or $k\geq 5$ then $C\leq \min\{\dfrac{15}{k-1},\dfrac{15}{6-k}\}\leq \dfrac{15}{4}$ .
If $k\in\{3,4\}$ then $C\leq \dfrac{45}{17}< \dfrac{15}{4}$ .
Hence, in all cases, we conclude $C\leq \dfrac{15}{4}$ .
To construct such a configuration that attains the maximum, consider two points $A,B$ , and assign $1$ to all segments involving either $A$ or $B$ , and $-7/8$ to all remaining segments. In this construction, the sum over any $6$ -point subset is exactly $15/4$ .
Thus, $C_{\max}=\dfrac{15}{4}$ .

This post has been edited 1 time. Last edited by internationalnick123456, Apr 21, 2025, 12:43 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a