Pigeonhole Problem: Prove that a subset's sum is divisible by 10

Question

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

Answer 1

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.