Maths Olympiad Prep

Library / /21 of 82

Combinatorics Difficulty 5.1 AIME, harder Prove it Croatia

Let AA be a subset of the set {1,2,3,,26}\{1, 2, 3, \dots, 26\} with seven elements. Prove that there are two distinct nonempty subsets of AA such that the sums of their elements are equal.

Solution

We prove a stronger statement that already among subsets of AA with at most four elements there are two with equal sums of elements. Set AA has
(71)+(72)+(73)+(74)=98 \binom{7}{1} + \binom{7}{2} + \binom{7}{3} + \binom{7}{4} = 98
subsets with at most four elements. The sum of elements of each of these subsets is at least 11 and at most 26+25+24+23=9826 + 25 + 24 + 23 = 98. Assume that among these subsets there are no two with equal sums of elements. Then every number between 11 and 9898 is the sum of elements of exactly one subset of AA with at most four elements. In particular, 9898 is the sum of the subset {23,24,25,26}A\{23, 24, 25, 26\} \subset A. On the other hand, two-element subsets {23,26}\{23, 26\} and {24,25}\{24, 25\} have equal sums, which is a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.