Given any nine numbers, prove there exists a subset of five numbers such that its sum is divisible by $5$. Given any nine numbers, prove there exists a subset of five numbers such that its sum is divisible by $5$.
I tried to take the numbers in the format $5k+1$, $5l+2$, and so on.  However, I am stuck in choosing ANY five from them...also,the numbers included in the subset may or may not belong to same format.
 A: We can prove the following more general result, which is a classical problem. The proof below is a classical one.
Lemma If $p$ is prime, then among any $2p-1$ numbers you can find $p$ whose sum is divisible by $p$.
Proof: Let $a_1,.., a_{2p-1}$ be the numbers. 
Consider all $n=\binom{2p-1}{p}$ subsets of $p$ numbers and denote by $S_1,...,S_n$ the sums of each subset.
Let 
$$S:= S_1^{p-1}+...+S_n^{p-1}$$
Let us observe first that $p|S$. 
Note that 
$$S_j^{p-1} = (a_{j_1}+...+a_{j_p})^{p-1}$$
 Any term in this sum has the form $a_{k_1}^{b_1}a_{k_2}^{b_2}...a_{k_l}^{b_l}$ with the coefficient being $\binom{p-1}{b_1,..,b_k}$.
Therefore $S$ is the sum of terms of this form. 
Now, let us check the coefficient of such a term. Whenever when this appears in some $S_j^{p-1}$ the coefficient is exactly $\binom{p-1}{b_1,..,b_l}$.
So we need to figure how many times does this appear in $S_j^{p-1}$. In order for this to happen, $a_1,a_2,..., a_l$ need to be $l$ of the $p-1$ terms, the other $p-l$ can be anything. Therefore, this appears in exactly $\binom{2p-1-l}{p-l}$ sums.  But since $p$ is prime, 
$$p| \frac{(2p-1-l)!}{(p-l)!(p-1)!}=\binom{2p-1-l}{p-l}$$
Now, if we assume by contradiction that none of $S_j$ is divisible by $p$, by Fermat Little Theorem we have
$$S= S_1^{p-1}+...+S_n^{p-1} \equiv 1+1+...+1 \equiv n \pmod{p}$$
But $n \not\equiv 0 \pmod{p}$ contradiction.
A: Just an idea, haven't yet finalized it.
$c_0$ - count numbers with remainder 0 mod 5
$c_1$ - count numbers with remainder 1 mod 5
$c_2$ - count numbers with remainder 2 mod 5
$c_3$ - count numbers with remainder 3 mod 5
$c_4$ - count numbers with remainder 4 mod 5    
It's clear that $c_k < 5$ for all $k$ (if it's not true, we'll pick the 5 numbers with same residue and problem is solved).
Also it's clear that at least one of $c_k$ is zero (if it's not we'll pick 1 number of each residue and problem is solved).   
Using these two observations, look at all possible cases about which $c_k$ exactly is zero. See if you can pick 5 numbers from the others which get the job done. 
... let me think further if we can further cut more of the logical branches ...   
A: Put them into five subsets according to their remainder mod 5.  You have [0],[1],[2],[3],[4].
If all five subsets contain a number, take one from each subset.
If only four subsets contain a number, then one contains at least three.  Suppose [a] contains three or more, [b] contains none.  Take three of [a], none of [b],none of [2a-b], and one each of the other two.  (Imagine we start with one from each group, but replace [b] and [2a-b] by two extra [a], the sum (mod 5) remains the same.)
If two or one subsets contain a number, take five from one subset.
Suppose three subsets [a],[b],[c] contain a number, but not [d] or [e].  Draw a regular pentagon with [0],[1],[2],[3],[4] in order at the corners.  By symmetry, you can relabel a,b,c so that [d+e]=[a+b]=[2c].  If possible, pick a+a+b+b+c, or a+b+c+c+c.  If that is impossible, then there is only one in [a], and also fewer than three in [c].  So there is at least six in [b], and you pick five from [b].
A: This can be solved using pigeonhole principle. Here is an idea :
You can group the pairs of numbers ending in different digits like $(1,4),(2,3),(3,2),(4,1)$ Now whenever you pick any 5 numbers at random, it is gurranteed that any one complete pair will be definitley picked (pigeonhole principle) 
$\implies$ the number will end in 5 $\implies$ divisible by 5.
Note it's just an idea, I will try it in more mathematical language.
