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.

  • $\begingroup$ It's not used anywhere, except that it's a (positive) number. You could have had the "element-product" for that matter. $\endgroup$ – Orest Bucicovschi Oct 13 '17 at 1:56
  • $\begingroup$ 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$"? $\endgroup$ – Natash1 Oct 13 '17 at 2:00
  • 1
    $\begingroup$ 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). $\endgroup$ – Orest Bucicovschi Oct 13 '17 at 2:07

The element sum is used indirectly, in the fact that, we only care for it's last two digits. There are less than one tenth the possible 2 digit endings, as there are subsets. Pigeonhole principle then implies that at least 11 subsets go to one of the subset sum endings.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.