1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It's not used anywhere, except that it's a (positive) number. You could have had the "element-product" for that matter. $\endgroup$
    – orangeskid
    Commented Oct 13, 2017 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
    Commented Oct 13, 2017 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$
    – orangeskid
    Commented Oct 13, 2017 at 2:07

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .