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.

Solution 1:

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.

Solution 2:

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 ...

Solution 3:

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].