1
$\begingroup$

Here is the problem:

Let $a_1,a_2,...,a_n$ be integers. Show that there exist integers $k$ and $r$ such that the sum $$a_k+a_{k+1}+...+a_{k+r}$$ is divisible by $n$.

My thoughts: I suppose we have to compare the residue of the runs modulo $n$. The pigeon hole principle should be applied too. I to find two runs of integers starting from the same integer with sums congruent modulo $n$ but I've been unable to do so. It'd be great if anyone can help.

$\endgroup$
2
  • 1
    $\begingroup$ You definitely don't need that the sequence is increasing... $\endgroup$ Dec 7, 2015 at 7:48
  • $\begingroup$ @ThomasAndrews Yeah... That was in a question set... It doesn't matter if the sequence is increasing or not... The logic would be the same... Anyway, I'll edit it... $\endgroup$ Dec 7, 2015 at 7:50

1 Answer 1

1
$\begingroup$

We shall look at the sums:

$0\\a_1\\a_1+a_2\\a_1+a_2+a_3\\...\\a_1+a_2+...+a_n$

There are $n+1$ numbers so two of them will have same remainder over $n$ and their difference is a multiple of $n$.

$\endgroup$
6
  • $\begingroup$ Yeah... I was so stupid to ask this... $\endgroup$ Dec 7, 2015 at 7:42
  • 1
    $\begingroup$ Nevermind, everyone gets trapped sometimes. $\endgroup$
    – cr001
    Dec 7, 2015 at 7:44
  • 1
    $\begingroup$ :/ :) I think we should really be able to add smileys... :P $\endgroup$ Dec 7, 2015 at 7:45
  • 1
    $\begingroup$ You can leave out $0$. If that counted then the question is trivial since $n$ divides $0$. Leaving it out, there is either a reside hit twice, or the residue $0$ is still hit somewhere. $\endgroup$
    – 2'5 9'2
    Dec 7, 2015 at 7:51
  • 1
    $\begingroup$ Yes you are right, I was just trying to avoid dividing into two cases and making the proof shorter. The logic is the same. $\endgroup$
    – cr001
    Dec 7, 2015 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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