Question

Let A be a set of 10 distinct integers between 1 and 100 (both inclusive). Show that there are two non-empty and disjoint subsets of A such that the sum of all its elements is the same.

Answer 1

The Pigeonhole Principle guarantees the existence of two non-empty and disjoint subsets of the set A (containing 10 distinct integers between 1 and 100, both inclusive) such that the sum of their elements is the same.

Step-by-step explanation:

Define 10 distinct integers between 1 and 100 as the elements of set A.

The sum of the integers in any subset of A will range from the minimum sum (1) to the maximum sum (the sum of all elements, which is 1 + 2 + ... + 100).

Since there are more subsets (2^10 = 1024) than the possible distinct sums, by the Pigeonhole Principle, at least two subsets must have the same sum.

Ensure that these subsets are also disjoint to meet the criteria of the problem.

Therefore, there exist two non-empty and disjoint subsets of A with the same sum.