HMMT 二月 2010 · GEN1 赛 · 第 2 题

HMMT February 2010 — GEN1 Round — Problem 2

[ 3 ] Let S = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } . How many (potentially empty) subsets T of S are there such that, for all x , if x is in T and 2 x is in S then 2 x is also in T ?

解析

[ 3 ] Let S = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } . How many (potentially empty) subsets T of S are there such that, for all x , if x is in T and 2 x is in S then 2 x is also in T ? Answer: 180 We partition the elements of S into the following subsets: { 1 , 2 , 4 , 8 } , { 3 , 6 } , { 5 , 10 } , { 7 } , { 9 } . Consider the first subset, { 1 , 2 , 4 , 8 } . Say 2 is an element of T . Because 2 · 2 = 4 is in S , 4 must also be in T . Furthermore, since 4 · 2 = 8 is in S , 8 must also be in T . So if T contains 2, it must also contain 4 and 8. Similarly, if T contains 1, it must also contain 2, 4, and 8. So T can contain the following subsets of the subset { 1 , 2 , 4 , 8 } : the empty set, { 8 } , { 4 , 8 } , { 2 , 4 , 8 } , or { 1 , 2 , 4 , 8 } . This gives 5 possibilities for the first subset. In general, we see that if T contains an element q of one of these subsets, it must also contain the elements in that subset that are larger than q , because we created the subsets for this to be true. So there are 3 possibilities for { 3 , 6 } , 3 for { 5 , 10 } , 2 for { 7 } , and 2 for { 9 } . This gives a total of 5 · 3 · 3 · 2 · 2 = 180 possible subsets T .