IMO 1972 Problem 1

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 20m29s

Problem

Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.

Exploration

Consider a set of ten distinct two-digit numbers, $S = {a_1, a_2, \dots, a_{10}}$, and examine the sums of all its non-empty subsets. There are $2^{10}-1 = 1023$ non-empty subsets. Each subset sum lies between the smallest element $a_{\min} \ge 10$ and the sum of all ten numbers, which is at most $90+91+\dots+99 = 945$. Therefore there are at most $945 - 10 + 1 = 936$ distinct sums. By the pigeonhole principle, at least two distinct subsets share the same sum.

The key challenge is to ensure these subsets are disjoint. The previous solution attempted to appeal to minimality among equal-sum subsets, but this argument fails because removing intersections changes the sum. To avoid this flaw, we test the general behavior of subsets of positive integers. If $X$ and $Y$ are distinct subsets with the same sum of strictly positive integers, neither can be properly contained in the other. Suppose $X \subset Y$ and $X \neq Y$; then $s(X) < s(Y)$ since all numbers are positive, which contradicts $s(X) = s(Y)$. This observation guarantees that for any two distinct equal-sum subsets, neither contains the other. Therefore, after removing their intersection, the residual subsets are non-empty and disjoint, giving two disjoint subsets with equal sums.

Small examples confirm this principle. For $S = {10,11,12,13}$, the subsets ${10,13}$ and ${11,12}$ both sum to $23$ and are disjoint. For $S = {10,11,12,13,14}$, the subsets ${10,14}$ and ${11,13}$ both sum to $24$ and are disjoint. Attempting to create overlapping equal-sum subsets that are nested fails because positive integers force strict inequalities in subset sums when one is contained in the other. Therefore, the corrected argument relies on the positivity of the elements to guarantee non-empty disjoint subsets.

Problem Understanding

The problem asks to show that from any set of ten distinct two-digit numbers, there exist two disjoint subsets with equal sums. The set $S$ is arbitrary but constrained to integers $10 \le a_i \le 99$. Non-empty subsets are considered, and the subsets must be disjoint, meaning no element belongs to both. The goal is to prove existence of such subsets for all ten-element sets of two-digit numbers.

The difficulty lies in ensuring disjointness. The standard pigeonhole argument guarantees equal sums among subsets, but overlapping subsets may not satisfy disjointness. The crucial observation is that subsets of positive integers with equal sums cannot be properly nested, which enables a valid transition to disjoint subsets.

Key Observations

There are $2^{10}-1 = 1023$ non-empty subsets of a ten-element set, and the subset sums lie in the range $[10, 945]$, giving at most $936$ possible sums. Therefore, some sum is repeated among distinct subsets.
If two distinct subsets $X$ and $Y$ of positive integers satisfy $s(X) = s(Y)$, neither is properly contained in the other. If $X \subset Y$ and $X \neq Y$, then $s(X) < s(Y)$, a contradiction.
Removing the intersection $X \cap Y$ from both $X$ and $Y$ yields subsets $X' = X \setminus (X \cap Y)$ and $Y' = Y \setminus (X \cap Y)$, which are disjoint. By Observation 2, neither $X'$ nor $Y'$ is empty, because proper containment is impossible.
Since $s(X) = s(Y)$, we have $s(X') + s(X \cap Y) = s(Y') + s(X \cap Y)$, which implies $s(X') = s(Y')$. Hence $X'$ and $Y'$ are non-empty disjoint subsets with equal sum.

Solution

Let $S = {a_1, a_2, \dots, a_{10}}$ be ten distinct two-digit integers. The number of non-empty subsets of $S$ is $2^{10}-1 = 1023$. Each subset sum $s(T)$ satisfies $10 \le s(T) \le 945$, giving at most $936$ distinct sums. By the pigeonhole principle, there exist distinct non-empty subsets $X$ and $Y$ such that $s(X) = s(Y)$.

Since all elements of $S$ are positive, $X$ cannot be properly contained in $Y$ and vice versa. Let $I = X \cap Y$, $X' = X \setminus I$, $Y' = Y \setminus I$. Then $X'$ and $Y'$ are disjoint, and since neither $X \subset Y$ nor $Y \subset X$, both $X'$ and $Y'$ are non-empty. Moreover,

$s(X') + s(I) = s(X) = s(Y) = s(Y') + s(I),$

so $s(X') = s(Y')$. Therefore $X'$ and $Y'$ are two non-empty disjoint subsets of $S$ with equal sum. This completes the proof.

∎

Verification of Key Steps

The pigeonhole principle is valid: $1023 > 936$, guaranteeing repeated sums among non-empty subsets. The claim that subsets of strictly positive integers cannot be properly nested with equal sum holds: if $X \subset Y$ and $X \neq Y$, then $s(X) < s(Y)$, a contradiction. Removing the intersection $I$ from $X$ and $Y$ produces disjoint subsets $X', Y'$ with equal sums because $s(X') = s(X) - s(I) = s(Y) - s(I) = s(Y')$. Both subsets are non-empty due to the impossibility of proper containment, ensuring the final subsets satisfy all conditions. Small numerical examples confirm this mechanism. Therefore, the argument is logically complete.

Alternative Approaches

One could use generating functions. Represent each number $a_i$ by the polynomial $x^{a_i}$ and consider the product $(1+x^{a_1})(1+x^{a_2})\dots(1+x^{a_{10}})$. The coefficient of $x^k$ counts the number of subsets summing to $k$. Since $2^{10}-1 > 936$, some coefficient is at least two, indicating repeated sums. The same argument regarding positivity of integers ensures that overlapping subsets cannot be nested, and removing intersections produces non-empty disjoint subsets with equal sum. Another approach is to consider the subsets modulo $k$ for suitable $k$, but the positivity argument gives the simplest elementary proof.