Kvant Math Problem 2834

Let the original integers be $a_1, a_2, \dots, a_n$ and let $S = a_1 + a_2 + \cdots + a_n$.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 19m28s
Source on kvant.digital

Problem

We call a set of numbers lucky if it cannot be partitioned into two nonempty groups such that the product of the sum of the numbers in one group and the sum of the numbers in the other group is positive. The teacher has written several integers on the board. Prove that the students can add one more integer to the existing ones so that the resulting set is lucky.

A. Kuznetsov

All-Russian Olympiad in Mathematics (LI, regional stage)

Exploration

Let the original integers be $a_1, a_2, \dots, a_n$ and let $S = a_1 + a_2 + \cdots + a_n$. We are allowed to add one integer $x$, forming the set ${a_1,\dots,a_n,x}$.

A partition into two nonempty groups corresponds to choosing a nonempty proper subset $A$ of the augmented set. If we denote $B$ as the complement, the condition that the set is not lucky means there exists $A$ such that

$\left(\sum_{a \in A} a\right)\left(\sum_{b \in B} b\right) > 0,$

so both sums are either strictly positive or strictly negative.

This suggests controlling the total sum after adding $x$, since for any subset $A$,

$\sum_{b \in B} b = (S + x) - \sum_{a \in A} a.$

If the total sum is forced to be $0$, then every pair of complementary sums is of the form $T$ and $-T$, whose product is always nonpositive. This immediately prevents the existence of a partition with positive product.

Thus the natural candidate is to choose $x = -S$.

A potential concern is whether some degenerate partition could violate the condition, but if the total sum is zero, the product structure becomes symmetric and always nonpositive, so no contradiction arises.

Problem Understanding

This is a Type D problem.

We are given an arbitrary finite set of integers. We must show that it is always possible to add one integer so that the resulting set has the property that no partition into two nonempty subsets yields two subset sums of the same strict sign.

The key idea is to enforce that the total sum of the new set becomes zero, which forces every partition to produce opposite-signed or zero-sum complementary parts, eliminating any possibility of a positive product.

The construction is expected to be the negation of the sum of the original numbers.

Proof Architecture

First, define the sum $S$ of the original set and choose $x = -S$, ensuring the augmented total sum equals zero.

Second, prove that for any partition of the augmented set into two nonempty subsets, the sums of the two parts are negatives of each other.

Third, show that the product of a number and its negative is nonpositive, which excludes positivity.

Fourth, verify that all partitions are covered, including those separating $x$ from the original elements.

The most delicate point is ensuring that every possible partition is accounted for under the symmetry induced by total sum zero.

Solution

Let the given integers be $a_1, a_2, \dots, a_n$, and let

$S = a_1 + a_2 + \cdots + a_n.$

Define the additional integer

$x = -S.$

After adding $x$, the total sum of all elements in the new set equals

$a_1 + \cdots + a_n + x = S - S = 0.$

Consider any partition of the augmented set into two nonempty disjoint subsets $A$ and $B$. Let

$s_A = \sum_{a \in A} a, \quad s_B = \sum_{b \in B} b.$

Since $A \cup B$ is the entire set, we have

$s_A + s_B = 0,$

hence

$s_B = -s_A.$

Therefore,

$s_A s_B = s_A(-s_A) = -s_A^2 \le 0.$

This shows that for every partition into two nonempty groups, the product of the sums of the two groups is never positive. Hence no partition satisfies the condition required to violate the “lucky” property, and the resulting set is lucky.

Thus the integer $x = -S$ ensures the desired property.

Verification of Key Steps

The critical identity $s_A + s_B = 0$ follows directly from the fact that $A$ and $B$ form a partition of a set whose total sum is zero; every element contributes exactly once to either $s_A$ or $s_B$, so their sum equals the total sum.

The sign condition reduces entirely to the algebraic expression $-s_A^2$, which is nonpositive for every real number $s_A$, including the case $s_A = 0$, where the product equals zero and still does not violate the required inequality.

Every partition, including those isolating the added element $x$, is covered because the derivation does not depend on the structure of $A$, only on completeness of the partition.

Alternative Approaches

An alternative viewpoint is to choose $x$ so that it dominates all partial sums of subsets of the original set in absolute value, forcing one of the two subset sums in any partition to change sign. This leads to more complicated bounding arguments and case analysis over subsets.

The zero-total-sum construction is preferable because it eliminates all case distinctions and reduces the problem to a single identity $s_B = -s_A$, making the argument fully uniform and algebraic.