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