返回题库

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

HMMT February 2006 — Guts Round — Problem 27

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. [9] Let N denote the number of subsets of { 1 , 2 , 3 , . . . , 100 } that contain more prime numbers k than multiples of 4. Compute the largest integer k such that 2 divides N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th IX HARVARD-MIT MATHEMATICS TOURNAMENT, 25 FEBRUARY 2006 — GUTS ROUND
解析
  1. Let N denote the number of subsets of { 1 , 2 , 3 , . . . , 100 } that contain more prime k numbers 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 the two. 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 in or 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 number 1 of primes and multiples of 4 if and only if S contains equal numbers as well. Let V 2 denote an arbitrary subset of T . It follows from examining pairs of sets V ∪ S and 1 V ∪ S that 2 ( ) ( ) 25 2 ∑ 1 25 50 50 N = 2 · 2 − 2 k k =0 ( ( )) 50 49 50 = 2 · 2 − 25 Since 50! is divisible by 2 exactly 25 + 12 + 6 + 3 + 1 = 47 times while 25! is divisible ( ) 50 by 2 exactly 12 + 6 + 3 + 1 = 22 times, it follows that is divisible by 2 exactly 3 25 times, so the answer is 49 + 3 = 52.