Here is the question: Let $S=\{1,2,3,…,99,100\}$ and let $B$ be a subset of $S$ with 48 elements. Show that $B$ has two distinct elements $x$ and $y$ whose sum is divisible by 11.
Usually while applying pigeon hole principle , I try to use pigeon holes according to question. I divided the set on basis of remainders it leaves. So there will be 11 sets
- $R_0$ leaving remainder 0,
- $R_1$ leaving 1
- and so on upto $R_{10}$.
Now $R_1$ will contain 10 elements and rest all $R_i$ will contain 9 elements. If we take $R_0,R_1,\ldots R_5$ on the left side and remaining $R_6, \ldots, R_{10}$ on the right side and try to choose $48$ elements, using PHP we will definitely end up taking at least three more elements from other side, two of which will add up to give multiple of 11.
But I feel like its too messy to write and understand. Is there a simple way of proving this question based on PHP?
Also please,tell how can I improve my usual approach of using PHP?
Best Answer
You begun excellently.
It is clear that at most one element from $R_0$ can be taken and put to $B.$
To make the solution a bit formal but not too complicated, set $$B=R_{i_1}\cup R_{i_2}\cup R_{i_3}\cup R_{i_4}\cup R_{i_5}$$ such that $i_k+i_l\neq 11$ and all of them verify $i_k\neq 11.$
For $|B|$ maximal, $B$ will contain all elements of $R_1$ (in your notation) and of four other sets $R_i$ except $R_{10}.$
This gives $10+9+9+9+9=46$ elements in $B.$ Adding one element from $R_{11}$ gives $$|B|=47.$$