2
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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, 2012 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, 2012 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, 2012 at 13:36

0

Reset to default

Browse other questions tagged or ask your own question.