HMMT 十一月 2009 · GEN1 赛 · 第 4 题

HMMT November 2009 — GEN1 Round — Problem 4

[ 4 ] How many subsets A of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } have the property that no two elements of A sum to 11?

解析

[ 4 ] How many subsets A of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } have the property that no two elements of A sum to 11? Answer: 243 For each element listed, there is exactly one other element such that the two elements sum to 11. Thus, we can list all the 10 numbers above as 5 pairs of numbers, such that each pair sums to 11. The problem then can be solved as follows: in any given subset with no two elements summing to 11, at most one element from each pair can be present. Thus, there are 3 ways in which each pair can contribute to a given subset (no element, the first element in the pair, or the second element in the pair). Since there are 5 pairs, the total number of ways to construct a subset with no two elements 5 summing to 11 is 3 = 243.