# 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

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