Maths Olympiad Prep

Library / /300 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

Find the number of subsets SS of {1,2,6}\{1,2, \ldots 6\} satisfying the following conditions: - SS is non-empty. - No subset of SS has the property that the sum of its elements is 10.

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

Solution

We do casework based on the largest element of SS. Call a set nn-free if none of its subsets have elements summing to nn. Case 1: The largest element of SS is 6. Then 4S4 \notin S. If 5S5 \notin S, then we wish to find all 4-free subsets of {1,2,3}\{1,2,3\} (note that 1+2+3=6<101+2+3=6<10). We just cannot include both 1,3, so we have 2(221)=62\left(2^{2}-1\right)=6 choices here. If 5S5 \in S, then we want 4,5-free subsets of {1,2,3}\{1,2,3\}. The only 4-but-not-5-free subset is {2,3}\{2,3\}, so we have 616-1 choices here, for a case total of 6+5=116+5=11. Case 2: The largest element of SS is 5. We seek 5,10-free subsets of {1,2,3,4}\{1,2,3,4\}. We just cannot have both 1,4 or both 2,3 (note that getting 10 requires the whole set), so we have (221)2=9\left(2^{2}-1\right)^{2}=9 subsets in this case. Case 3: The largest element of SS is at most 4. (So we want a 4-free subset of {1,2,3,4}\{1,2,3,4\}.) The only way to sum to 10 with 1,2,3,41,2,3,4 is by using all the terms, so we simply discount the empty set and {1,2,3,4}\{1,2,3,4\}, for a total of 242=142^{4}-2=14 subsets. In conclusion, the total number of subsets is 11+9+14=3411+9+14=34.

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