Browse · MathNet
PrintMathematica competitions in Croatia
Croatia counting and probability
Problem
Let be a subset of the set with seven elements. Prove that there are two distinct nonempty subsets of such that the sums of their elements are equal.
Solution
We prove a stronger statement that already among subsets of with at most four elements there are two with equal sums of elements. Set has subsets with at most four elements. The sum of elements of each of these subsets is at least and at most . Assume that among these subsets there are no two with equal sums of elements. Then every number between and is the sum of elements of exactly one subset of with at most four elements. In particular, is the sum of the subset . On the other hand, two-element subsets and have equal sums, which is a contradiction.
Techniques
Pigeonhole principle