XbenX wrote: For any edge $AB$ we call a cuttlefish the set of all edges from $A$ and $B$ (including $AB$). What does this mean? Does it mean the set of edges incident to at least one of $A$ or $B$?

XbenX wrote: Let $G$ be a graph with $400$ vertices. For any edge $AB$ we call a cuttlefish the set of all edges from $A$ and $B$ (including $AB$). Each edge of the graph is assigned a value of $1$ or $-1$. It is known that the sum of edges at any cuttlefish is greater than or equal to $1$. Prove that the sum of the numbers at all edges is at least $10^4$. I don't think this is the correct statement. Consider a linear graph with $400$ vertices, and a $1$ at every edge. Then the value of every cuttlefish is $\ge 2$, and the sum over all edges is $399$, unless I am miscomputing.

Maybe the graph is complete?

The statement is ok, I checked the Russian text. A cuttlefish is the set of edges incident to $A$ or $B$ (providing $AB$ is an edge). The example in #3 doesn't contradict to the statement since $399>-10000$. In other words it should be proved the negative edges couldn't be too many.

dgrozev wrote: The statement is ok, I checked the Russian text. A cuttlefish is the set of edges incident to $A$ or $B$ (providing $AB$ is an edge). The example in #3 doesn't contradict to the statement since $399>-10000$. In other words it should be proved the negative edges couldn't be too many. There was a negative sign missing in the statement (as can be seen in the quote in my post), which has now been corrected

Please tell me I'm not high Choose the largest matching $M = \{v_1-w_1,v_2-w_2,\dots v_n-w_n\}$ in the graph. Let $N$ be the set of vertices not in $M$, then $N$ is an independent set. If $N = \emptyset$ then summing along edges $v_iw_i$, each edge's weight is counted twice except for those joining a pair in $M$, so the total edge sum is $\ge \frac{n - n}{2} = 0 \ge 10^{-4}$. From now on assume that $N$ is nonempty, then $|N| =400 - 2n \ge 2$. Since there are no $n_1, n_2 \in N$ and $i \in \{1,\dots,n\}$ with $v_1-v_i, v_2 - w_i$ it follows that for each edge $v_iw_i$ the number of edges from $N$ into $v_iw_i$ is at most $400-2n$. Now we sum along the edges of the matching as before, the number of edges counted $1\times$ is $\le (401-2n)n$ so that the total sum of edge weights is $$\ge \frac{n-(401-2n)n}{2} = (n-200)n \ge -10^4,$$as desired.

@stroller: Splendid! I admit, I gave a try, but didn't manage to finish it. So, the idea is to take the largest matching and count the tagged numbers on the cuttlefishes of the connected pairs. I put some more explanations on the above solution in my blog.

wow thanks for confirming this... the problem is quite a hit-or-miss