Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Welcome to MSE. :-) –  user21436 Feb 24 '12 at 15:06
    
Thank you, Kannappan! –  Sidharth Iyer Feb 24 '12 at 15:15
2  
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 2

up vote 4 down vote accepted

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

share|improve this answer
    
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$$

share|improve this answer
    
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
    
I get it now! My apologies. –  Sidharth Iyer Feb 24 '12 at 17:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.