Sum of $n$ integers from set of size $2n-1$ divides $n$

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$.