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

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

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

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.