Lesson 7

Proof. The total number of non-empty subsets is \(2^{30}-1>10^{9}\) (the total number of subsets, including the empty one, is \(2^{30}\), because each element can be included or not). On the other hand, the sum of the elements of each such subset is not more than \(30 \cdot 10^{7}=0.3 \cdot 10^{9}\). Therefore, there will be two non-empty sets with the same sum. If they intersect, then the repeated elements can be removed from both sets. It is easy to see that non-empty disjoint sets with the same sum will be obtained.◼