Kvant Math Problem 490

Let the given integers be $a_1,\dots,a_{p-1}$, none divisible by $p$.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m24s
Source on kvant.digital

Problem

$p$ is an odd prime number. Given $p-1$ integers not divisible by $p$. Prove that by replacing some of these integers with their opposites, one can obtain $p-1$ numbers whose sum is divisible by $p$.

S. V. Fomin

Exploration

Let the given integers be $a_1,\dots,a_{p-1}$, none divisible by $p$. Replacing some numbers by their opposites means choosing signs $\varepsilon_i\in{\pm1}$ and seeking

$$\varepsilon_1a_1+\cdots+\varepsilon_{p-1}a_{p-1}\equiv0\pmod p.$$

The problem is purely modular. Since every $a_i$ is nonzero modulo $p$, each $a_i$ has a multiplicative inverse modulo $p$.

It is natural to test small primes.

For $p=3$, there are two nonzero residues. We need signs for $a_1,a_2$. Modulo $3$, the possible sums are

$$\pm a_1\pm a_2.$$

If $a_1\equiv a_2$, choosing opposite signs gives $0$; if $a_1\equiv -a_2$, choosing the same signs gives $0$.

For $p=5$, there are four numbers. The statement resembles a subset-sum problem. Writing

$$\sum \varepsilon_i a_i = \sum a_i-2\sum_{i\in S}a_i,$$

where $S$ is the set of indices whose signs are changed, the condition becomes

$$2\sum_{i\in S}a_i\equiv \sum_{i=1}^{p-1}a_i\pmod p.$$

Since $2$ is invertible modulo the odd prime $p$, this asks for a subset whose sum is a prescribed residue modulo $p$.

Thus the problem becomes:

Given $p-1$ nonzero residues modulo $p$, prove that the set of all subset sums contains every residue class modulo $p$.

This looks plausible because there are $2^{p-1}$ subsets, far more than $p$ residues. A counting argument alone is insufficient because many subsets may have the same sum.

A standard inductive fact comes to mind: if $A_k$ is the set of subset sums of $k$ nonzero residues modulo $p$, then either $|A_{k+1}|>|A_k|$ or $A_k$ already equals all residues. Indeed,

$$A_{k+1}=A_k\cup(A_k+a_{k+1}).$$

If $A_k+a_{k+1}=A_k$, then $A_k$ is invariant under translation by a nonzero residue. Repeated translations generate all residues modulo $p$, forcing $A_k=\mathbb Z/p\mathbb Z$. Otherwise the size increases.

Starting from $|A_0|=1$, after adjoining $p-1$ nonzero elements the size must increase at each step until it reaches at most $p$. Hence after $p-1$ steps it has size at least $p$, so exactly $p$. Therefore every residue occurs as a subset sum.

The delicate point is proving that invariance under translation by one nonzero residue implies the set is the whole residue class ring.

Problem Understanding

We are given $p-1$ integers, none divisible by the odd prime $p$. We may independently replace any of them by its opposite. We must prove that the resulting $p-1$ numbers can be chosen so that their sum is divisible by $p$.

This is a Type B problem.

The core difficulty is to show that among all possible sign choices, one produces a sum congruent to $0$ modulo $p$. After rewriting the sign condition, the problem becomes a statement about subset sums modulo $p$: every residue class modulo $p$ must occur as a subset sum of the given $p-1$ nonzero residues.

Proof Architecture

Let $b_i$ be the residues of the given integers modulo $p$; each $b_i\neq0$.

Define $A_k$ to be the set of subset sums formed from $b_1,\dots,b_k$. Then $A_{k+1}=A_k\cup(A_k+b_{k+1})$. This follows directly from whether a subset uses $b_{k+1}$.

If $A_k+b_{k+1}=A_k$ and $b_{k+1}\neq0$, then $A_k=\mathbb Z/p\mathbb Z$. Repeated translation by $b_{k+1}$ reaches every residue modulo $p$.

If $A_k\neq\mathbb Z/p\mathbb Z$, then $|A_{k+1}|>|A_k|$. Otherwise the two sets in the union would coincide, contradicting the previous lemma.

Inductively, $|A_k|\ge k+1$ for $0\le k\le p-1$. Starting from $|A_0|=1$, the size increases by at least $1$ until it reaches $p$.

Hence $|A_{p-1}|=p$, so every residue class is a subset sum.

Choosing a subset whose sum is half of the total sum modulo $p$ yields the required sign assignment.

The lemma most likely to fail under scrutiny is the claim that translation invariance by one nonzero residue forces a subset of $\mathbb Z/p\mathbb Z$ to be the whole group.

Solution

Reduce all given integers modulo $p$. Let their residues be

$$b_1,b_2,\dots,b_{p-1},$$

where each $b_i\not\equiv0\pmod p$.

Let

$$T=b_1+\cdots+b_{p-1}\pmod p.$$

Suppose there exists a subset $S\subseteq{1,\dots,p-1}$ such that

$$\sum_{i\in S} b_i\equiv \frac{T}{2}\pmod p.$$

Since $p$ is odd, $2$ is invertible modulo $p$, so $T/2$ is well defined modulo $p$.

For such a subset, replace $b_i$ by $-b_i$ precisely when $i\in S$. The resulting sum is

$$T-2\sum_{i\in S} b_i \equiv T-2\cdot\frac{T}{2} \equiv0 \pmod p.$$

Thus it suffices to prove that every residue modulo $p$, and in particular $T/2$, occurs as a subset sum of the numbers $b_1,\dots,b_{p-1}$.

For $k=0,1,\dots,p-1$, let $A_k$ denote the set of all subset sums formed from $b_1,\dots,b_k$:

$$A_k= \left{ \sum_{i\in I} b_i \pmod p : I\subseteq{1,\dots,k} \right}.$$

We have $A_0={0}$, so $|A_0|=1$.

For $k<p-1$,

$$A_{k+1}=A_k\cup(A_k+b_{k+1}),$$

where

$$A_k+b_{k+1} = {x+b_{k+1}:x\in A_k}.$$

Consider a fixed $k<p-1$.

If

$$A_k+b_{k+1}=A_k,$$

then $A_k$ is invariant under addition of the nonzero residue $b_{k+1}$. Hence for every $x\in A_k$ and every integer $m$,

$$x+mb_{k+1}\in A_k.$$

Since $b_{k+1}\not\equiv0\pmod p$ and $p$ is prime, the residues

$$0,b_{k+1},2b_{k+1},\dots,(p-1)b_{k+1}$$

are all distinct modulo $p$. They constitute all residue classes modulo $p$. Taking any $x\in A_k$, the residues

$$x+mb_{k+1}\qquad (m=0,1,\dots,p-1)$$

also constitute all residue classes modulo $p$. Hence $A_k=\mathbb Z/p\mathbb Z$.

Consequently, if $A_k\neq\mathbb Z/p\mathbb Z$, then

$$A_k+b_{k+1}\neq A_k.$$

Since translation preserves cardinality,

$$|A_k+b_{k+1}|=|A_k|.$$

The union

$$A_{k+1}=A_k\cup(A_k+b_{k+1})$$

is then strictly larger than $A_k$, so

$$|A_{k+1}|>|A_k|.$$

Now $|A_k|\le p$ for every $k$, because there are only $p$ residue classes. Starting from $|A_0|=1$, the cardinality increases by at least $1$ whenever it is less than $p$. By induction,

$$|A_k|\ge k+1$$

for all $k$.

In particular,

$$|A_{p-1}|\ge p.$$

Since $A_{p-1}$ is a subset of the $p$ residue classes modulo $p$, we obtain

$$|A_{p-1}|=p.$$

Thus

$$A_{p-1}=\mathbb Z/p\mathbb Z.$$

Every residue modulo $p$ is therefore a subset sum of $b_1,\dots,b_{p-1}$. In particular, there exists a subset $S$ with

$$\sum_{i\in S} b_i\equiv \frac{T}{2}\pmod p.$$

As shown at the beginning, changing the signs of exactly those terms indexed by $S$ produces a total sum congruent to $0$ modulo $p$.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the passage from sign choices to subset sums. If $S$ is the set of indices whose signs are changed, then the new sum equals

$$\sum_{i\notin S} b_i-\sum_{i\in S} b_i = T-2\sum_{i\in S} b_i.$$

The condition for divisibility by $p$ is

$$T-2\sum_{i\in S} b_i\equiv0\pmod p,$$

which is equivalent to

$$\sum_{i\in S} b_i\equiv T/2\pmod p.$$

The use of $T/2$ is legitimate only because $p$ is odd.

The second delicate step is proving that $A_k+b=A_k$ with $b\neq0$ implies $A_k=\mathbb Z/p\mathbb Z$. From $A_k+b=A_k$ one gets $A_k+mb=A_k$ for every integer $m$. Fixing any $x\in A_k$, all residues $x+mb$ belong to $A_k$. Because $b\neq0$ modulo the prime $p$, multiplication by $b$ permutes the residue classes, so the $p$ values $x+mb$ cover all residues. Hence $A_k$ contains every residue class.

The third delicate step is the growth estimate. When $|A_k|<p$, the previous lemma shows that $A_k+b_{k+1}\neq A_k$. Since the two sets have equal cardinality, their union must contain strictly more elements than either set alone. This yields

$$|A_{k+1}|>|A_k|.$$

Without the equality of cardinalities under translation, the argument would be incomplete.

Alternative Approaches

The subset sums can also be viewed through the polynomial

$$\prod_{i=1}^{p-1}(1+x^{b_i})$$

in the group algebra of $\mathbb Z/p\mathbb Z$. The coefficient of $x^r$ counts subsets whose sum is congruent to $r$. A standard argument using the nontrivial characters of the cyclic group of order $p$ shows that if some residue class were missing, then evaluating the polynomial at a primitive $p$th root of unity would force a contradiction, because every factor $1+\zeta^{b_i}$ is nonzero when $p$ is odd.

The combinatorial growth argument used above is preferable here because it avoids character sums and uses only elementary properties of translations in the cyclic group $\mathbb Z/p\mathbb Z$. The proof remains entirely within the scope of elementary olympiad methods.