1
$\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$
  • $\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 '17 at 3:02
  • $\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$ – Gerry Myerson Dec 8 '17 at 3:06
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$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.