3
$\begingroup$

Given a sequence of $10$ integers, show that there is a subset of consecutive integers whose sum is divisible by $10$

Suppose I have subsets

$$\{a_1\}$$

$$\{a_1,a_2\}$$

$$\vdots$$

$$\{a_1,a_2,a_3,a_4, \dots, a_{10}\}$$

I am stuck on what to do to prove this. Am I suppose to somehow use $a_i \equiv a_j \pmod{10}$ for $i \neq j $?

$\endgroup$
  • $\begingroup$ Why have you assumed that the first of the consecutive integers is always $a_1$? $\endgroup$ – Shaun Aug 21 at 22:26
4
$\begingroup$

Consider the sums $a_1$, $a_1+a_2$, ..., $a_1+a_2+...+a_{10}$. If any of those are divisible by 10, you are done. Otherwise, the ten have the remainders 1 through nine, and therefore two of them have the same remainder modulo 10 by the Pigeonhole Principle. Let $i$ and $j$ be those two numbers. Then $$a_{i+1}+...+a_j=(a_1+...+a_j)-(a_1+...+a_i)$$ is surely divisible by 10.

$\endgroup$
  • $\begingroup$ They will all have remainders, and since there's 10 subsets two will have the same remainder. Where do i go from here. Is the difference of these subsets divisible by 10 or is this the wrong way to go $\endgroup$ – Kevin G Aug 21 at 22:16
  • $\begingroup$ Proof expanded. $\endgroup$ – Matthew Daly Aug 21 at 22:23
  • $\begingroup$ There's actually 1023 nonempty subsets @KevinG $\endgroup$ – Roddy MacPhee Sep 1 at 23:32

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.