Can anyone suggest a reference or a simple proof of the following?

For every sequence of integers $a_1,...,a_n$, there exists a non-empty subsequence whose sum is divisible by $n.$

Here is a more general problem: Prove that for every $r$ and $n$ there is $k$ such that for every sequence of vectors $v_1,...,v_k \in {\mathbb Z}^r$ there exists a subsequence whose sum belongs to $(n{\mathbb Z})^r$. (I would think that $k=n^r$ should be enough...)


closed as too localized by Steven Landsburg, Andreas Blass, Anthony Quas, Joe Silverman, Douglas Zare Jul 28 '12 at 2:20

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ This looks like fodder for stackexchange, or better yet artofproblemsolving (I think the latter is a sufficient hint). Yes, your conjectured generalization works, even in an arbitrary finite group with $k$ being the group order. $\endgroup$ – Noam D. Elkies Jul 28 '12 at 1:50
  • 2
    $\begingroup$ In case for the higher dimensional problem you need more than that bound you mention the key-word to look for is Davenport constant (of a finite abelian group). Indeed, exact value guaranteeing this is open (for general n) if r >= 3; but for prime power n or r=2 it is known that the simple lower bound 1 + r (n-1) is in fact the exact value. And no longer example is know for any pair (r,n). However, for general finite abelian groups (ie different moduli in different coordinates) there are examples known that are larger than the 'obvious' lower bound. $\endgroup$ – user9072 Jul 28 '12 at 13:11
  • $\begingroup$ Thanks quid! Davenport constant indeed is what I was looking for. As for the requested proof, (in case somebody wonders) I realized that indeed it is very easy with my suggested bound: by contradiction: If $S_k=\sum_{i=1}^k v_i \ne 0$ mod $n$ for $k=1,...,n^r$ then $S_k=S_l$ for some $k<l$ and $S_l-S_k$ is the desired subsequence. $\endgroup$ – Adam Jul 28 '12 at 13:36

Browse other questions tagged or ask your own question.