HMMT 二月 2017 · COMB 赛 · 第 9 题

英文解析

9. Let m be a positive integer, and let T denote the set of all subsets of { 1 , 2 , . . . , m } . Call a subset Sof 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
   ( )
   ∑
   | ∆( s , s ) | ≥ δm.ni j
   1 ≤ i<j ≤ n 2
   On the other hand, for 1 ≤ i ≤ m , let t = |{ 1 ≤ j ≤ n : i ∈ s }| . Then it is clear thati j
   2 m
   ∑ ∑
   | ∆( s , s ) | = t ( n − t ) ≤ mni j k k
   1 ≤ i<j ≤ n k =14
   by AM-GM. Therefore, we get the bound
   ( )
   n n 2 δ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 beinterpreting the integers 1 , 2 , . . . , m as 11-digit integers in binary. Given this interpretation, define adot 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 . } .
   A computation shows that this construction works.i
   Some notes: here is the motivation behind the construction. We are treating the integers 0 , 1 , . . . , m asthe vector space V = F , and the sets s correspond to linear functionals f : V → F . In particular,11
   i i 2
   the function f : V → F is simply defined as f ( x ) = ( i − 1) x , which one can easily check to be 2
   i 2 ilinear. This construction corresponds to Hadamard matrices of size 2 .11