12
$\begingroup$

Given any multiset of positive integers of size $2n-1$, is it possible to find a multisubset of size $n$ such that $n$ divides the sum of the integers in this multisubset?

This problem has been circulating for a while in my friends group and none of us has been able to solve it.

Someone in the friend group has claimed there is a solution using the Chevalley–Warning theorem, but has not actually shown us such a solution.

A multiset is a set that may contain a number more than once.

$\endgroup$
5
$\begingroup$

The answer is yes. We prove it when $n$ is a prime number using the Chevalley-Warning theorem, then we generalize to any integer $n$.

Let $p$ be a prime number. Given $2p-1$ integers $a_1,\dotsc,a_{2p-1}$, there exists a subset $I \subset \{1,\dotsc,2p-1\}$ containing $p$ elements such that $\sum_{i\in I} a_i =0 \pmod p$.

Recall the Chevalley-Warning theorem : let $p$ be a prime number, $q$ be a power of $p$, $\mathbb{F}_q$ be the finite field with $q$ elements, and $(P_\alpha)_{\alpha\in A}$ be a family of elements of $\mathbb{F}_q[X_1,\dots,X_m]$ such that $\sum_{\alpha\in A} \deg{P_\alpha}<m$, and let $V=\{x \in \mathbb{F}_q^m \mid P_\alpha(x)=0 \quad \forall \alpha \in A\}$. Then $\operatorname{Card}{V}=0 \pmod{p}$.

Now we set $q=p$, and

$$ \begin{align} P_1(X_1,\dotsc,X_{2p-1})&=\sum_{i=1}^{2p-1}X_i^{p-1}, \\ P_2(X_1,\dotsc,X_{2p-1})&=\sum_{i=1}^{2p-1}a_iX_i^{p-1}. \end{align} $$

Our family $(P_1,P_2)$ of polynomials satisfies the requirement of the theorem since $\deg{P_1}+\deg{P_2}=2p-2<2p-1$. So $p$ divides the cardinal of $V$, but since $V$ contains the trivial solution $(0,\dotsc,0)$, there exists another (non-trivial) solution $(x_1,\dots,x_{2p-1}) \in (\mathbb{F}_p)^{2p-1}$.

Let $I=\{1\leq i \leq 2p-1 \mid x_i \neq 0\}$. Since

$$ x_i^{p-1}=\begin{cases} 1 &\text{if $x_i\neq 0$} \\ 0 &\text{if $x_i =0$} \end{cases}, $$

we have

$$0=P_1(x_1,\dotsc,x_{2p-1})=(\operatorname{Card}{I})\mathbb{1}_{\mathbb{F}_p},$$

where $(\operatorname{Card}{I})\mathbb{1}_{\mathbb{F}_p}$ is to be understood as the sum of $\operatorname{Card}{I}$ copies of the unity element of $\mathbb{F}_p$. So $\operatorname{Card}{I}=0 \pmod p$, hence $\operatorname{Card}{I}$ equals $0$ or $p$. But $I$ is nonempty, so $\operatorname{Card}{I}=p$.

We also have

$$0=P_2(x_1,\dotsc,x_{2p-1})=\left(\sum_{i\in I} a_i\right)\mathbb{1}_{\mathbb{F}_p}, $$

so $\sum_{i\in I} a_i=0 \pmod p$ and the result follows.

Let $n$ be any positive integer. Given $2n-1$ integers $a_1,\dotsc,a_{2n-1}$, there exists a subset $I \subset \{1,\dotsc,2n-1\}$ containing $n$ elements such that $\sum_{i\in I} a_i =0 \pmod n$.

We prove this property $\mathcal{P}(n)$ by induction. If $n$ is a prime number, the result follows from the first part of my answer. So we can assume that $n=uv$ where $u<n$ and $v<n$ are two positive integers. Let us also assume that the propositions $\mathcal{P}(u)$ and $\mathcal{P}(v)$ are true.

Since we have $2n-1>2u-1$ integers, we can select $u$ of them so that their sum is divisible by $u$ : let $I_1$ be that subset, and consider the remaining $2n-u-1$ integers :

$$(a_i)_{i \in \{1,\dotsc,2n-1\}\setminus I_1}. $$

We then repeat the process of selecting $u$ of them, etc. We can do that exactly $2v-1$ times, after what there are only $2n-1-(2v-1)u=u-1$ integers left, and we can toss those.

Now let $S_1=\sum_{i\in I_1} a_i, \dotsc, S_{2v-1}=\sum_{i \in I_{2v-1}} a_i$. We write $S_j=uS_j'$ where $S_j'$ are integers. From the sequence $(S_1',\dots,S_{2v-1}')$, one can apply the proposition again : there exists $J\subset \{1,\dots,2v-1\}$ such that

$$ \sum_{j\in J} S_j' = 0 \pmod v. $$

By letting $I=\cup_{j \in J} I_j$ we have

$$ \sum_{i\in I} a_i = 0 \pmod n, $$

which is what we wanted since $\operatorname{Card}{I}=uv=n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.