Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S_{k}$ be the set of sequences of natural numbers of length $k$.

For a natural number $n$ what is the least $k$ s.t. every element in $S_{k}$ has a subsequence $a_{0},a_{1},...,a_{i}$ for $i \leq k$ for which the sum of terms in the subsequence is divisible by $n$. That is

$$\sum_{0\leq j \leq i} a_{j} \equiv 0\pmod n $$

A lower bound is easy. $k \geq n$ since $S_{k}$ contains a sequence of $k$ $1$s.

Note that for calculation it suffices to consider the sequences of numbers mod $n$. The calculations I have done suggest $k=n$ which I hope is true since it would give a solution to another problem I'm interested in.

share|cite|improve this question
Do you require the subsequence to start at $0$ ? Because if you do, then the sequence $1,0,0,\ldots$ has no "subsequence divisible by $n$". – Joel Cohen Mar 3 '12 at 23:48
No I don't require the subsequence to start at 0. – David Marquis Mar 3 '12 at 23:59
up vote 3 down vote accepted

Given a sequence $a_1,a_2,\dots,a_k$, consider the numbers $$0,a_1, a_1+a_2, a_1+a_2+a_3, \dots, a_1+\cdots+a_k$$ If any two are equal modulo $n$, then their difference is a subsequence which sums to zero modulo $n$. So, how large can $k$ be, and still have all these numbers unequal modulo $n$?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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