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

  • 1
    Welcome to MSE. :-)2012-02-24
  • 0
    Thank you, Kannappan!2012-02-24
  • 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
    Doesn't this mean that $m$ and $n$ are not necessarily unique? Observe that, in the case $k$ $=$ $3$, $m$ and $n$ are unique for a chosen $a$, $b$, $c$. This proof only illustrates the existence of such an $m$ and $n$ but doesn't ascertain the uniqueness.2012-02-24
  • 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
    You are allowed to choose only $k$ $=$ $3$ number of integers.2012-02-24
  • 0
    @SidharthIyer: But that isn't what the question says... and Andre also seems to have interpreted it like I did.2012-02-24
  • 0
    The question mentions thus: Let $a_1$$;$ $a_2$; $...;$ $a_k$ be $k$ positive integers.2012-02-24
  • 0
    @SidharthIyer: $a_1 = a_2 = \dots = a_6 = 2$ are $6$ positive integers. Any run of $3$ has a sum divisible by $6$. So $m$ and $n$ are not unique. What am I missing?2012-02-24
  • 0
    I get it now! My apologies.2012-02-24
  • 0
    @SidharthIyer: No worries!2012-02-24