regarding Pigeonhole principle

Let A be a set of 100 natural numbers.
prove that there is a set B $$B\subseteq A$$
such that the sum of B’s elements can be divided by 100

I am stuck for a few days now. Please help!

Solutions Collecting From Web of "regarding Pigeonhole principle"

take a chain of subsets of $A$, $\emptyset\subset\{a_1\}\subset\{a_1,a_2\}\subset…\subset A$. this chain has 101 elements. now sort them by their sum modulo 100. two of the sets in the chain must be equal modulo 100. hence there is $n>m$ with
$
(0+a_1+…+a_n)-(0+a_1+…+a_m)
$
divisible by 100, so that $a_{m+1}+…+a_n$ is divisible by 100.


here is a more detailed explanation:

let $A_0=\emptyset, A_i=\{a_1,a_2,…,a_i\}$ where $A=\{a_1,…,a_{100}\}$. let $s_0=0, s_i=\sum_{k=1}^ia_k$. we have 101 numbers $s_0,…,s_{100}$ which we will sort into 100 groups $G_0,…,G_{99}$. we put $s_i$ in group $G_r$ if the remainder after dividing $s_i$ by $100$ is equal to $r$. since there are 101 numbers $s_i$ and only $100$ groups, one of the groups $G_r$ will have at least two numbers $s_n,s_m$ in it (without loss of generality, $n>m$ since one of them will have bigger subscript). if $s_n=100k+r$ and $s_m=100l+r$ then $s_n-s_m=100(k-l)$ is divisible by $100$. by construction, the number $s_n-s_m$ is precisely the sum $a_{m+1}+…+a_n$ corresponding to the subset $A_n\backslash A_m$ of $A$ (note that $A_n$ is not empty because $n>m\geq0$ and that $A_m$ is a proper subset of $A_n$ so that the difference $A_n\backslash A_m$ is nonempty).

Use induction with the statement being “a subset for each number smaller or equal than n’, then look at the numbers mod 100. Add the new number to an appropriate subset mod 100 (this is where the pigeonhole principle comes in). For induction root look at cases of even and odd numbers (to do 1 and 2).