HMMT 二月 2017 · COMB 赛 · 第 9 题
HMMT February 2017 — COMB Round — Problem 9
题目详情
- Let m be a positive integer, and let T denote the set of all subsets of { 1 , 2 , . . . , m } . Call a subset S of T δ - good if for all s , s ∈ S , s 6 = s , | ∆( s , s ) | ≥ δm , where ∆ denotes symmetric difference (the 1 2 1 2 1 2 symmetric difference of two sets is the set of elements that is in exactly one of the two sets). Find the 1024 largest possible integer s such that there exists an integer m and a -good set of size s . 2047
解析
- Let m be a positive integer, and let T denote the set of all subsets of { 1 , 2 , . . . , m } . Call a subset S of T δ - good if for all s , s ∈ S , s 6 = s , | ∆( s , s ) | ≥ δm , where ∆ denotes symmetric difference (the 1 2 1 2 1 2 symmetric difference of two sets is the set of elements that is in exactly one of the two sets). Find the 1024 largest possible integer s such that there exists an integer m and a -good set of size s . 2047 Proposed by: Yang Liu Answer: 2048 ∑ Let n = | S | . Let the sets in S be s , s , . . . , s . We bound the sum | ∆( s , s ) | in two ways. 1 2 n i j 1 ≤ i<j ≤ n On one hand, by the condition we have the obvious bound ( ) ∑ n | ∆( s , s ) | ≥ δm. i j 2 1 ≤ i<j ≤ n On the other hand, for 1 ≤ i ≤ m , let t = |{ 1 ≤ j ≤ n : i ∈ s }| . Then it is clear that i j m 2 ∑ ∑ n | ∆( s , s ) | = t ( n − t ) ≤ m i j k k 4 1 ≤ i<j ≤ n k =1 by AM-GM. Therefore, we get the bound ( ) 2 n n 2 δ δm ≤ m ⇒ n ≤ = 2048 . 2 4 2 δ − 1 To give a construction with n = 2048, take m = 2047 . For the rest of this construction, we will be interpreting the integers 1 , 2 , . . . , m as 11-digit integers in binary. Given this interpretation, define a dot product x y of two positive integers 0 ≤ x, y ≤ m the following way. If x = ( x x . . . x ) , y = 1 2 11 2 ( y y . . . y ) in binary, then 1 2 11 2 ∑ x y = x y (mod 2) . i i Now we can define the sets s , s , . . . , s . Define 1 2 2048 s = { 1 ≤ j ≤ m : ( i − 1) j = 1 . } . i A computation shows that this construction works. Some notes: here is the motivation behind the construction. We are treating the integers 0 , 1 , . . . , m as 11 the vector space V = F , and the sets s correspond to linear functionals f : V → F . In particular, i i 2 2 the function f : V → F is simply defined as f ( x ) = ( i − 1) x , which one can easily check to be i 2 i 11 linear. This construction corresponds to Hadamard matrices of size 2 .