HMMT 二月 2006 · 冲刺赛 · 第 27 题

英文解析

27. Let N denote the number of subsets of { 1 , 2 , 3 , . . . , 100 } that contain more primeknumbers than multiples of 4. Compute the largest integer k such that 2 divides N .
    Answer: 52
    Solution: Let S denote a subset with the said property. Note that there are 25
    multiples of 4 and 25 primes in the set { 1 , 2 , 3 , . . . , 100 } , with no overlap between thetwo. Let T denote the subset of 50 numbers that are neither prime nor a multiple of 4,
    and let U denote the 50 other numbers. Elements of T can be arbitrarily included inor excluded by S . Consider S ∩ U = S and U − S = S (the set difference is defined
    1 2
    to be all elements of U that are not in S .) S and S are two disjoint sets such that
    1 2
    U = S ∩ S . If S contains more multiples of 4 than primes, then S contains more
    1 2 1 2
    primes than multiples of 4, and conversely. Furthermore, S contains an equal numberof primes and multiples of 4 if and only if S contains equal numbers as well. Let V1
    denote an arbitrary subset of T . It follows from examining pairs of sets V ∪ S and 2
    V ∪ S that 1
    ( )2
    ( )
    ∑225
    1 25
    50 50
    N = 2 · 2 −
    2 kk =0
    ( ( ))
    49 5050 = 2 · 2 −
    Since 50! is divisible by 2 exactly 25 + 12 + 6 + 3 + 1 = 47 times while 25! is divisible 25
    ( )
    by 2 exactly 12 + 6 + 3 + 1 = 22 times, it follows that is divisible by 2 exactly 350
    times, so the answer is 49 + 3 = 52.25