6
$\begingroup$

What I've observed: Pick any $3$ random positive integers, say $a$, $b$, $c$ which are not of the form $0\pmod{3}$ then one and only one of $a+b$, $b+c$, $c+a$, $a+b+c$ is always a multiple of $3$.

What I've generalized: Let $a_1$$;$ $a_2$; $...;$ $a_k$ be $k$ positive integers with $a_r$ $\not=$ $0\pmod{k}$ $\forall$ $1$ $\le$ $r$ $\le$ $k$. Then there exist $m$ and $n$ with $1$ $\le$ $m$ $\le$ $n$ $\le$ $k$ such that $\sum_{i=m}^n a_i$ is divisible by $k$.

My question: Whether or not such a generalization is true.

Note: The condition $a_r$ $\not=$ $0\pmod{k}$ $\forall$ $1$ $\le$ $r$ $\le$ $k$ is given to avoid the trivial solution, it being $m$ $=$ $n$ $=$ $r$.

  • 2
    A friendly note: `\not=` has the same effect as `\neq` but at the cost of one character less. :-)2012-02-24

2 Answers 2

4

Yes, it is true. The restriction to positive integers is not necessary. Consider $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, and so on up to $a_1+a_2+\cdots+a_k$. There are $k$ (not necessarily distinct) sums here.

If one of these sums is congruent to $0$ modulo $k$, we are finished. Otherwise, there are at most $k-1$ values modulo $k$ that these sums can assume.

Then, by the Pigeonhole Principle, two of the sums are congruent modulo $k$, say $\sum_{i=1}^{m-1} a_i$ and $\sum_{i=1}^n a_i$, where $m \le n$. But then their difference $\sum_{i=m}^n a_i$ is congruent to $0$ modulo $k$.

  • 0
    @Sidharth Iyer: Your formulation of the generalization did not specify uniqueness. And we cannot have uniqueness. For example with $n=k$ look at $1, 3, 1, 3$. there are several sums divisible by $4$. The uniqueness of the sum that gives$a$result divisible by $k$ does not continue when k>3.2012-02-24
1

Counterexample to uniqueness:

$2,2,2,2,2,2$

  • 0
    @SidharthIyer: No worries!2012-02-24