2
$\begingroup$

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.

  • 0
    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$".2012-03-03
  • 0
    No I don't require the subsequence to start at 0.2012-03-03

1 Answers 1

3

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