0

Given $n$ natural numbers $m_1, ..., m_n$, of which none is divisible by $n$, I want to prove that there exist an $i \in \{2, ..., n\}, k \in \mathbb{N}$, so that the sum of exactly $i$ of the given numbers is equal to $k n$.

I must admit that I didn't really have a great approach yet. I thought t hat one could reduce the case by taking $m_1, ..., m_n\space mod \space n$, so therefore only consider some numbers in $\{1, 2, ..., n-1\}$, and subsequently show that there are two or more of them out of this set which sum is equal to $k n$ with a $k \in \mathbb{N}$. But that didn't really help so far.

(Also, I'm searching for a proof that doesn't use induction; I'm not that sure anyway if it can be solved using induction.)

moran
  • 3,047

1 Answers1

4

List your elements in whatever order you like, $\{a_1,\dots , a_n\}$ and look at the partial sums $$S_k=\sum_{i=1}^k S_i \mod n$$

There are $n$ such sums, hence either every residue class is hit or we have some residue class that has two partial sums in it, say $S_j$ and $S_l$ for $l>j$. But in the latter case the sum $$S_l-S_j = a_{j+1}+\dots + a_l \equiv 0 \mod n$$

lulu
  • 70,402