2
$\begingroup$

Consider a set A of 10 integers, $A= \{a_1,a_2, \ldots ,a_{10}\}$. Prove that there is at least one subset of A whose sum is divisible by 10. Use the pigeon-hole principle. Hint: Consider the 10 sums $s_1 = a_1, s_2 = a_1 + a_2, \ldots ,s_{10} = a_1 + a_2 + \ldots+a_{10}$. If one of these ten sums is divisible by $10$, we are done. So assume that none of these ten sums is divisible by $10$.

I'm pretty sure this is the proof but im not exactly sure what's $b_l$ and $b_k$ stand for?

Let $A=\{a_1,a_2,...,a_{10}\}$ Define set of numbers $b_n=\sum\limits_{i=1}^n a_n$ i.e. the set $$\{a_1, (a_1+a_2),(a_1+a_2+a_3),\ldots ,(a_1+a_2+\ldots +a_{10})\}$$
If any element of the set is divisible by $10$, then we are done.

Hence proving case $1$.

Case 2: Assume that no element of this set is disible by $10$.

Then, by Pigeon hole priciple, there exists some $k<l$, such that, $b_l\equiv b_k$

then $b_l\equiv b_k (mod 10)$ with $l>k>0$

Hence, $\{b_k,b_{k+1}, \ldots,b_l\}$ is a subset of $A$ whose sum is divisble by $10$. Thus proving Case $2$.

$\endgroup$
2
  • 1
    $\begingroup$ There are only 10 possible remainders, and you have 10 elements $b_i$. If none are divisible by 10, you have only 9 potential remainders, so 2 must double up. Hmm... $\endgroup$
    – Randall
    Dec 8, 2017 at 3:02
  • 1
    $\begingroup$ Nothing in the way the question is stated rules out the empty set, which is a subset of $A$ and has sum zero, which is divisible by 10. Presumably, one wants to ask for a nonempty subset of $A$. $\endgroup$ Dec 8, 2017 at 3:06

2 Answers 2

2
$\begingroup$

This is a general proof for:

In a list of $N$ integers, there exists a non-empty subset of this list whose sum is divisible by $N$.

Statement $1$: If $a_1$ and $a_1+a_2+a_3$ have the same remainder when divided by $N$, $a_2+a_3$ must be divisible by $N$.

We define a set $A$ with $N$ elements (this is our list): $$A = \{a_1,a_2,a_3...a_N\}$$ Then we define $B$ as a set where $B_n = \sum_{i=1}^{n}a_i$ $$B = \{a_1,a_1+a_2,a_1+a_2+a_3...B_N\}$$ When a number is divided by $N$, there are $N$ possible remainders $(0,1,2...N-1)$. We have $N$ elements in $B$. If every remainder is different, one of the remainders must be $0$, therefore, we have a subset whose sum is divisible by $N$. However, if not every remainder is different, then at least two numbers must share a remainder (pigeonhole principle). By statement $1$, we see that there is a subset whose sum is divisible by $N$. We can then have any $N$ and this proof will hold up.

$\endgroup$
1
$\begingroup$

$$b_n = \sum_{i=1}^n a_n.$$

$b_n$ is the sum of the first $n$ $a_i$'s.

In terms of modulo $10$, since none of them is $0 \mod 10$, by pigeonhole principle, we can find a pair of $b_i$, call them $b_l$ and $b_k$ such that

$$ b_l \equiv b_k \pmod{10}.$$

Hence $b_k - b_l \equiv 0 \pmod{10}$,

Hence $\sum_{n=k+1}^la_n$ is divisible by $10$.

Hence $\color{red}{\{a_{k+1}, \ldots, a_l\}}$ is one such subset.

I have highlighted a potential fix for a typo in your proof.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .