Prove that among any 101 distinct positive integers, there exists 11 numbers with a sum divisible by 11.
I have tried to seperate the 101 positive integers into 10 sets such that 1 set has at least 11 integers, but I do not know what to do from here.
Break the sets according to their class mod 11 (the remainder upon dividing by 11). There are two cases: either every subset will be non-empty, or one subset will be missing. If a subset is missing, then you have 10 subsets, and one will have size at least 11. The sum of any 11 elements in that subset will be a multiple of 11. If every subset is non-empty, then take one element from each subset. Then their sum will be $0+1+2+3+...+10=0 \pmod{11}$.
Let $A$ be this set of 101 distinct positive integers. For $n\in\{0,...,10\}$ we define $$A_n:=\{a\in A:a\equiv n\text{ (mod }11)\}.$$ We can notice that $A_n\cap A_m=\emptyset$ for $n\neq m$. If there exists $n_0\in\{0,...,10\}$ such that $\#A_{n_0}\geq 11$, then we just pick 11 elements from this set, their sum will be divisible by 11. Now let's assume that $$\forall_{n\in\{0,...,10\}}:\#A_n\leq 10.$$ We can notice that all $A_n$ must be non-empty (if one was empty, then we would have $\#(\bigcup_nA_n)\leq 100$ which is a contradiction). Therefore we can pick one element from each $A_n$. The sum is $0+1+...+9+10=55$ which is divisible by 11.
