# Pigeonhole principle explanation

Let $A$ be any set of $10$ positive integers.
Prove that there must exist at least $11$ subsets of $A$ having their element-sum with the same last $2$ digits.
(Here element-sum means sum of all elements in the set)

Answer: Let $A$ be a set of any $10$ positive integers.
So $|A| = 10$. So, the set of all subsets of $A$ has cardinality $2^{10} = 1024$.
Now, there are $10^2 = 100$ ways for the last two digits of a number.
Let the pigeonholes be these "ways".
So, there is one pigeonhole (one number with some ending two digits) containing $\lceil \frac{1024}{10} \rceil = 11$ subsets of $A$.

I'm unsure why we had to mention "element-sum" as I don't see where it's used in the proof.

• It's not used anywhere, except that it's a (positive) number. You could have had the "element-product" for that matter. – Orest Bucicovschi Oct 13 '17 at 1:56
• So usually it's just good to have some sort of property about the sets? (e.g. maybe "... subsets of $A$ having each element raised to a power of $4$"? – Natash1 Oct 13 '17 at 2:00
• In this case you are using very little information about the actual numbers. Of course, since it's just a rough estimate, $11$ may not be the best result there. The result is more like this: say we have $2^10$ positive integers. Show that there are at least $11$ of them that give the same remainder when divided by $100$. You don't need to know how the numbers were obtained, only that there are (at least) $1024$ of them ( in fact $1001$ would do). – Orest Bucicovschi Oct 13 '17 at 2:07