Kvant Math Problem 1040

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m36s
Source on kvant.digital

Problem

The numbers 1, 2, $\ldots$, $3n$ are divided arbitrarily into three groups of $n$ numbers each. Prove that it is possible to choose one number from each group such that one of them equals the sum of the other two.

V. B. Alekseev, S. Savchev (Bulgaria)

Exploration

For $n=1$ the three groups are ${1},{2},{3}$, and $3=1+2$.

For $n=2$, consider a partition such as ${1,6}$, ${2,5}$, ${3,4}$. Then $1+3=4$, with the three numbers taken from different groups. The statement survives a rather unbalanced partition.

The numbers involved lie in ${1,\dots,3n}$. A relation of the form $a+b=c$ is naturally represented by an edge joining $a$ and $b$ and labeled by $c$. Since the groups form a 3-coloring of the set ${1,\dots,3n}$, the problem asks for a monochromatic obstruction: prove that some solution $a+b=c$ uses all three colors.

A useful observation is that for every $k\le n$,

$$k+(2n+1-k)=2n+1.$$

Thus there are $n$ different representations of the number $2n+1$ as a sum of two numbers. If $2n+1$ belongs to one group, then every one of those $n$ pairs must fail to have its two members in the other two groups simultaneously, otherwise we are done.

Suppose $2n+1$ is in group $C$. Let $A,B,C$ denote the three groups. For each pair

$${k,,2n+1-k},$$

if one element lies in $A$ and the other in $B$, then together with $2n+1\in C$ we obtain the desired triple. Hence every pair is either entirely inside $A\cup C$ or entirely inside $B\cup C$.

This suggests counting. Let $x$ be the number of such pairs contained in $A\cup C$, and $y$ the number contained in $B\cup C$. Then $x+y=n$.

Each pair of the first type contributes at least one element to $A\cup C$, and similarly for the second type. The crucial point is to count how many elements of $A$ and $B$ can occur. Writing the numbers in the interval $[1,2n]$ as these $n$ pairs may force one of the groups $A$ or $B$ to contain too few elements.

A cleaner route emerges by considering Hall's theorem. Let $2n+1\in C$. Form a bipartite graph between the pairs

$$P_k={k,2n+1-k}$$

and the groups $A,B$. Connect $P_k$ to a group if the pair contains a member of that group. If some pair meets both $A$ and $B$, we are done. Hence every pair is connected to at most one of $A,B$. Then all pairs are assigned to either $A$ or $B$ or neither. Counting the $n$ elements of $A$ and the $n$ elements of $B$ against the $2n$ numbers participating in the pairs should yield a contradiction.

Let $a$ be the number of pairs containing an element of $A$. Since no pair meets both $A$ and $B$, every element of $A$ lies in a distinct assigned pair, so $a=n$. Similarly the number of pairs containing an element of $B$ is $n$. But there are only $n$ pairs altogether. This contradiction is the key.

Indeed, each element of $A$ belongs to exactly one pair $P_k$, and if a pair containing an element of $A$ also contained an element of $B$, we would already be finished. Therefore every pair containing an element of $A$ contains no element of $B$. Distinct elements of $A$ belong to distinct pairs, so all $n$ pairs contain an element of $A$. The same argument shows all $n$ pairs contain an element of $B$. Hence every pair contains both an element of $A$ and an element of $B$, contradicting the assumption that none does. This is the core insight.

Problem Understanding

The set ${1,2,\dots,3n}$ is partitioned into three groups $A,B,C$, each containing exactly $n$ numbers. We must prove that there exist numbers $a\in A$, $b\in B$, $c\in C$ such that one of them equals the sum of the other two.

This is a Type B problem. The statement to be proved is given in advance.

The core difficulty is to use only the equal sizes of the three groups. The special number $2n+1$ provides $n$ disjoint representations

$$2n+1=k+(2n+1-k),$$

which cover all numbers from $1$ to $2n$. These representations interact strongly with the condition that each group has exactly $n$ elements.

Proof Architecture

Let $A,B,C$ be the three groups, and assume $2n+1\in C$.

Lemma 1: If some pair ${k,2n+1-k}$ contains one element of $A$ and one element of $B$, then the theorem is proved, because together with $2n+1\in C$ they form a triple satisfying $k+(2n+1-k)=2n+1$.

Lemma 2: Under the negation of the theorem, every pair ${k,2n+1-k}$ contains no elements from both $A$ and $B$ simultaneously, because such a pair would yield the configuration of Lemma 1.

Lemma 3: Under the same assumption, every pair contains an element of $A$, because the $n$ elements of $A$ lie among the $n$ disjoint pairs and no two elements of $A$ can belong to the same pair.

Lemma 4: Symmetrically, every pair contains an element of $B$.

The hardest step is Lemma 3, where one must use both the disjointness of the pairs and the fact that $|A|=n$.

Solution

Let the three groups be denoted by $A$, $B$, and $C$, each of cardinality $n$. Renaming the groups if necessary, assume that

$$2n+1\in C.$$

Consider the $n$ disjoint pairs

$$P_k={k,,2n+1-k}, \qquad k=1,2,\dots,n.$$

These pairs partition the set ${1,2,\dots,2n}$.

Assume that the statement of the problem is false. Then there do not exist numbers chosen from the three different groups such that one equals the sum of the other two.

By Lemma 1, no pair $P_k$ can contain one element of $A$ and one element of $B$, because then together with $2n+1\in C$ we would obtain

$$k+(2n+1-k)=2n+1,$$

with the three numbers belonging to the three different groups.

Hence every pair $P_k$ contains at most one of the groups $A$ and $B$.

Now consider the elements of $A$. There are exactly $n$ of them. Since the pairs $P_1,\dots,P_n$ are disjoint and cover ${1,\dots,2n}$, two different elements of $A$ cannot lie in the same pair. Indeed, if some pair contained two elements of $A$, then among the $n$ pairs there would be at most $n-1$ pairs containing elements of $A$, which is impossible because $A$ has $n$ elements and each element belongs to one of the pairs.

Thus each of the $n$ elements of $A$ lies in a different pair. Since there are exactly $n$ pairs, every pair contains an element of $A$.

The same argument applied to $B$ shows that every pair contains an element of $B$.

Consequently every pair $P_k$ contains both an element of $A$ and an element of $B$. This contradicts the earlier conclusion that no pair contains elements from both groups simultaneously.

The contradiction arose from assuming that the theorem was false. Therefore such a choice of three numbers always exists.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the deduction that no pair $P_k$ contains one element from $A$ and one from $B$. If such a pair existed, say

$$P_k={x,y},$$

with $x\in A$ and $y\in B$, then

$$x+y=2n+1.$$

Since $2n+1\in C$, the numbers $x$, $y$, and $2n+1$ belong to three different groups and satisfy the required additive relation. This directly contradicts the assumption that no such triple exists.

The second delicate point is proving that every pair contains an element of $A$. There are $n$ elements of $A$ and exactly $n$ disjoint pairs. If some pair contained no element of $A$, then the remaining $n-1$ pairs would have to accommodate all $n$ elements of $A$. By the pigeonhole principle, one of those pairs would contain at least two elements of $A$. Such a pair would then contain no element of $B$, because a pair containing both colors $A$ and $B$ is forbidden. Repeating the counting for $B$ yields a contradiction. The shorter argument in the proof packages this counting into the statement that the $n$ elements of $A$ occupy $n$ distinct pairs.

The final contradiction is exact. From the $A$-count every pair contains an element of $A$; from the $B$-count every pair contains an element of $B$. Hence each pair contains both colors, which is precisely what had been ruled out.

Alternative Approaches

A graph-theoretic proof can be given. Let the vertices be the numbers $1,\dots,3n$. Join $k$ and $2n+1-k$ for each $k\le n$. This produces a perfect matching on the first $2n$ numbers. Coloring vertices by the three groups, the desired configuration is equivalent to the existence of an edge whose endpoints have the two colors different from the color of $2n+1$. Assuming no such edge exists, every matching edge misses at least one of those two colors. Since each of the two color classes has size $n$, counting incidences between color classes and matching edges forces every edge to contain both colors simultaneously, yielding a contradiction.

Another approach uses Hall-type counting. The pairs $P_k$ form $n$ containers for the $n$ elements of $A$. If no pair contains both an $A$-element and a $B$-element, then each pair can serve at most one of the color classes. Since both $A$ and $B$ have size $n$, all $n$ pairs are required by $A$ and also all $n$ pairs are required by $B$, which is impossible. The direct counting argument used in the main proof is essentially this idea stripped to its simplest form.