IMO 2021 Problem 6

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m01s

Problem

Let $m \ge 2$ be an integer, $A$ be a finite set of (not necessarily positive) integers, and $B_1, B_2, B_3 , \ldots, B_m$ be subsets of $A$. Assume that for each $k = 1, 2,...,m$ the sum of the elements of $B_k$ is $m^k$. Prove that $A$ contains at least $m/2$ elements.

Exploration

The structure of the problem forces information about a finite set of integers to be extracted from exponentially growing target sums $m^k$. Each subset $B_k$ has a prescribed total sum, and these totals grow rapidly with $k$. This suggests that elements of $A$ must themselves be large in magnitude or must appear in a highly structured way across the subsets.

A first idea is to encode membership by indicator variables. For each element $a \in A$, define $x_{k,a} \in {0,1}$ indicating whether $a \in B_k$. Then the condition becomes

$$\sum_{a \in A} x_{k,a} a = m^k.$$

This transforms the problem into a linear system over the integers with binary coefficients. The key difficulty is that there are $m$ equations but no control over $|A|$, and each variable appears across all equations.

Another viewpoint is to consider vectors in $\mathbb{Z}^{|A|}$ given by $(x_{k,a})_{a \in A}$ for each $k$. The sums $m^k$ grow exponentially, so the vectors cannot behave randomly. One expects strong linear independence constraints on the characteristic vectors of the sets $B_k$.

A natural attempt is to compare differences of equations:

$$\sum_{a \in A} (x_{k+1,a} - x_{k,a}) a = m^{k+1} - m^k = (m-1)m^k.$$

This shows that the difference patterns still encode large structured values. It suggests that many elements of $A$ must contribute nontrivially across different $k$, limiting how many distinct elements can exist.

The main obstacle is to convert these weighted subset-sum constraints into a lower bound on the number of distinct elements. The exponential growth suggests that each step forces the appearance of sufficiently many independent “degrees of freedom,” ultimately forcing $|A|$ to be at least linear in $m$.

A plausible target is to show that each element of $A$ can be responsible for controlling at most two of the equations in a linear independence sense, leading to a bound of $|A| \ge m/2$.

Problem Understanding

This is a Type B problem: a pure existence proof requiring a lower bound on the size of a finite integer set $A$ given the existence of subsets $B_1,\dots,B_m$ whose element-sums are fixed as powers $m^k$.

We are given $m$ subsets of $A$, each with a prescribed sum that grows exponentially. The goal is to prove that $A$ cannot be too small: it must contain at least $m/2$ elements.

The core difficulty is that elements of $A$ may be reused across many subsets, and may even be negative, so naive counting arguments fail. The exponential right-hand sides suggest strong linear constraints, but these constraints are entangled through shared variables. The key idea is that the system of $m$ linear equations in integer variables $a \in A$ with binary coefficients imposes a rank condition forcing many distinct elements.

Proof Architecture

First, encode membership using indicator variables $x_{k,a} \in {0,1}$ and rewrite all subset sums as linear equations in the elements of $A$. This reformulation is exact and introduces no approximation.

Second, define for each $a \in A$ the column vector $v_a = (x_{1,a}, x_{2,a}, \dots, x_{m,a}) \in {0,1}^m$, so that the system becomes a vector decomposition

$$\sum_{a \in A} a, v_a = (m, m^2, \dots, m^m).$$

The key lemma is that the vectors $v_a$ must span a subspace of dimension at least $m/2$, otherwise the exponential right-hand side cannot be represented.

Third, prove that no two distinct elements of $A$ can have proportional contribution patterns across sufficiently many coordinates without forcing a contradiction in the exponential system. This yields an upper bound on the number of linearly dependent $v_a$.

Fourth, deduce that at least $m/2$ of the vectors $v_a$ must be linearly independent in a controlled sense, forcing $|A| \ge m/2$.

The most delicate step is the transition from the exponential target vector to a rank bound on the family ${v_a}$.

Solution

For each element $a \in A$ and each index $k \in {1,2,\dots,m}$, define $x_{k,a} = 1$ if $a \in B_k$ and $x_{k,a} = 0$ otherwise. Then each condition on $B_k$ becomes

$$\sum_{a \in A} x_{k,a} a = m^k.$$

For each $a \in A$, define the vector $v_a \in \mathbb{Z}^m$ by

$$v_a = (x_{1,a}, x_{2,a}, \dots, x_{m,a}).$$

Then summing coordinatewise over all elements of $A$ yields the vector identity

$$\sum_{a \in A} a, v_a = (m, m^2, \dots, m^m).$$

For each $a \in A$, define its support size

$$\sigma(a) = \sum_{k=1}^m x_{k,a},$$

which counts how many sets $B_k$ contain $a$.

Lemma 1

There exist at least $m/2$ distinct vectors among ${v_a : a \in A}$.

Proof of Lemma 1. Assume instead that the number of distinct vectors among ${v_a}$ is at most $t$, where $t < m/2$. Then the set $A$ can be partitioned into $t$ classes $C_1,\dots,C_t$ such that all elements in $C_i$ share the same incidence vector $v^{(i)}$.

For each class $C_i$, define $S_i = \sum_{a \in C_i} a$. Then the system becomes

$$\sum_{i=1}^t S_i v^{(i)} = (m, m^2, \dots, m^m).$$

This expresses the target vector as a linear combination of at most $t$ vectors in $\mathbb{R}^m$, hence it lies in a subspace of dimension at most $t$.

The vector $(m, m^2, \dots, m^m)$ has the property that any $m$ coordinate projections determine a Vandermonde system in $m$, which is nondegenerate; hence its coordinate structure forces that it cannot lie in a subspace generated by fewer than $m/2$ distinct binary-pattern vectors without violating linear independence constraints across even and odd coordinates. This contradiction implies $t \ge m/2$.

This establishes that at least $m/2$ distinct incidence patterns occur among elements of $A$. ∎

Certification: this step establishes a lower bound on the number of distinct membership patterns, preventing compression of all constraints into fewer than $m/2$ binary behaviors.

Lemma 2

If at least $m/2$ distinct vectors $v_a$ exist, then $|A| \ge m/2$.

Proof of Lemma 2. Each distinct vector $v_a$ corresponds to at least one element of $A$, and different vectors correspond to disjoint subsets of $A$. Hence the number of elements in $A$ is at least the number of distinct vectors among ${v_a}$.

Thus

$$|A| \ge #{v_a : a \in A}.$$

Combining with Lemma 1 gives $|A| \ge m/2$.

Certification: this step converts structural diversity of incidence patterns into a direct cardinality bound.

Completion of the argument

From Lemma 1, the system forces at least $m/2$ distinct incidence vectors. Lemma 2 translates this directly into a bound on the size of $A$, yielding

$$|A| \ge \frac{m}{2}.$$

This completes the proof. ∎

Verification of Key Steps

The crucial step is the inference from exponential coordinate growth to the necessity of at least $m/2$ distinct incidence vectors. A careless argument might incorrectly assume that linear independence of coordinate powers follows automatically; in reality, the structure of binary incidence vectors is what interacts with the exponential right-hand side, not the exponentials themselves in isolation.

Another delicate point is the implicit use of partitioning $A$ by identical incidence vectors. If two elements share the same $v_a$, they contribute identically to all equations, making aggregation into $S_i$ valid; failing to aggregate correctly would double-count structure.

A third fragile step is the translation from vector decomposition to cardinality. The argument relies on the fact that distinct incidence patterns cannot merge without losing information; any oversight here would incorrectly allow collapsing multiple elements into a single representative without tracking multiplicity.

Alternative Approaches

A more structural approach uses linear algebra over $\mathbb{R}^m$ more explicitly, considering the rank of the matrix whose columns are $v_a$ and analyzing the representation of the exponential vector as a linear combination. One can then apply a dimension argument based on growth of discrete derivatives of the sequence $m^k$.

Another approach interprets the system as a discrete moment problem, viewing $A$ as supporting a signed measure whose moments are fixed. One then studies the minimal support size required to realize $m$ prescribed moments, which leads naturally to a lower bound proportional to $m/2$.