Maths Olympiad Prep

Library / /276 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

2. 18 The sum of a set of numbers is the sum of all its elements. Let SS be a set of positive integers not exceeding 15, such that the sums of any two disjoint subsets of SS are not equal, and among all sets with the above property, the sum of SS is the largest. Find the sum of the set SS.

A number or a short expression. Spacing and $ signs are ignored.

Solution

[Solution] We first prove that SS has at most 5 elements.
In fact, if SS has at least 6 elements, then the number of non-empty subsets of SS with at most 4 elements is at least
C61+C62+C63+C64=56 (subsets) C_{6}^{1}+C_{6}^{2}+C_{6}^{3}+C_{6}^{4}=56 \text { (subsets) }

The sums of these subsets do not exceed 54 (i.e., 15+14+13+12=5415+14+13+12=54). By the pigeonhole principle, among 56 positive integers not exceeding 54, at least two numbers are equal, i.e., at least two subsets have the same sum. If these two subsets are disjoint, it contradicts the condition that "the sums of any two disjoint subsets of SS are not equal." If these two subsets intersect, removing the common elements still leads to a contradiction.

Therefore, SS has at most 5 elements.
Next, we construct this 5-element set to maximize the elements (and thus maximize the sum of the set).
After SS contains 15,14,1315, 14, 13, it cannot contain 12, otherwise 15+12=14+1315+12=14+13;
SS can contain 11, but it cannot contain 10 and 9, otherwise 15+10=14+11,15+15+10=14+11, 15+
9=13+11;9=13+11;

The last element is 8, then
S={15,14,13,11,8}15+14+13+11+8=61\begin{array}{l} S=\{15,14,13,11,8\} \\ 15+14+13+11+8=61 \end{array}

Thus, the largest possible sum is 61.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.