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. - Welcome to MSE. :-) – user21436 Feb 24 '12 at 15:06 Thank you, Kannappan! – Sidharth Iyer Feb 24 '12 at 15:15 A friendly note: \not= has the same effect as \neq but at the cost of one character less. :-) – user21436 Feb 24 '12 at 15:15 ## 2 Answers 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. - 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. – Sidharth Iyer Feb 24 '12 at 16:13 @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. – André Nicolas Feb 24 '12 at 17:31 Counterexample to uniqueness:$$2,2,2,2,2,2$$- You are allowed to choose only k = 3 number of integers. – Sidharth Iyer Feb 24 '12 at 16:29 @SidharthIyer: But that isn't what the question says... and Andre also seems to have interpreted it like I did. – Aryabhata Feb 24 '12 at 16:31 The question mentions thus: Let a_1$$;$ $a_2$; $...;$ $a_k$ be $k$ positive integers. –  Sidharth Iyer Feb 24 '12 at 16:42
@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? –  Aryabhata Feb 24 '12 at 16:53