Injective Function and Pigeonhole principle.

Question

I'm reading the Book of Proof textbook and I got stuck on the following example question:

Proposition: If A is any set of 10 integers between 1 and 100, then there exist two different subsets X ⊆ A and Y ⊆ A for which the sum of elements in X equals the sum of elements in Y.

Textbook Solution: Suppose A ⊆ {1,2,3,4,...,99,100} and |A| = 10. Notice that if X ⊆ A, then X has no more than 10 elements, each between 1 and 100, and therefore the sum of all the elements of X is less than 100·10 = 1000. Consider the function f : P(A) → {0,1,2,3,4,...,1000} where f(X) is the sum of the elements in X. As |P(A)| = 2^10 = 1024 > 1001 = |{0,1,2,3,...,1000}| it follows from the pigeonhole principle that f is not injective.

Here are my confusions about this example:

1) From the above: "therefore the sum of all the elements of X is less than 100·10 = 1000". I'm not certain why the sum must be less than 100·10. Is it because that the set X may be {100,100,100,100,100,100,100,100,100,100}, so its sum would be 100·10? Since the problem did't state whether the values from 1 to 100 can be repeated. But from my understanding, {100,100,100,100,100,100,100,100,100,100} = {100}...but the elements can't repeat since |P(A)| = 2^10 tells us that the power set of a set with 10 elements is 2^10, which means that there are 2^10 combinations of different sums, so it can't have repeating elements such that {ten 100s} and in this case, it should be less than or equals to 91+92+...+100 = 955 to make it more precise?

2) "As |P(A)| = 2^10 = 1024 > 1001 = |{0,1,2,3,...,1000}|", why does the set contains a zero in output set "{0,1,2,3,...,1000}". Since the set A contains only numbers from 1 to 100, there is no sum of any elements of the subsets of A that is equals to zero. I'm thinking that since X ⊆ A, then null set is in set X, so the sum of an empty set is zero? I'm not sure if this logic is correct.

Thanks for the help.

Answer 1

For (1)

You're right that there can be no repetitions, your subset can't have $100$ ten times. But whatever it has, $100 \times 10$ must be greater than the sum, so the sum is less than $1000$.

For (2)

Your right that the sum can't be $0$ so there is one fewer possible value.

But for the pigeonhole principle argument to work all you need is an inequality. The bounds from both (1) and (2) are good enough. No need to work harder to improve them.

Answer 2

1) $\sum\limits_{x\in Y\subset A} x \le 955 < 100*10 < 1024$.

So you are correct that $955$ is a more precise upper bound. But that doesn't make the proof wrong. $100*10$ is still an upper bound. And so long as it is less than $1024$ the proof is valid.

2) $\sum\limits_{x \in \emptyset \subset A} x = 0$. So $0$ is a valid sum. Of course $0$ is only achieved via the emptyset so we know there aren't any other with a sum of $0$. We also know that if $\{1\} \subset A$ that that is the only subset with a sum of $1$. So you only have to consider $P(A) \to \{2,3,4....,955\}$ which has $954$ elements and .... again $954 < 1001 < 1024$

But pointing those exceptions out does nothing to make the proof any easier. Quite the opposite in fact. Pointing out $0$ and $1$ are unique sums and the maximum value is $91 + 92 + .... + 100 = 955$ are distracting and irrelevant tangents. If we were proving a much tighter result, it's conceivable that we'd need to use them but as our inequality is still good... why bother?

And again... being more precise does not make a less precise proof wrong.