HMMT 二月 2003 · 团队赛 · 第 6 题

英文解析

6. Prove that any 2-configuration containing e elements is m -separable for some m ≤
   √
   1 1 + 2 e + .
   2 4
   Solution: Suppose m is the minimum integer for which the given configuration C onset A is m -separable, and fix a corresponding labeling of the elements of A . Let A bethe set of all elements with the label i . Then, for any i, j with 1 ≤ i < j ≤ m , thereimust exist a ∈ A , a ∈ A with { a , a } ∈ C , since otherwise the elements of A couldi i j j i j jhave been reassigned the label i , decreasing the number of distinct labels necessary and
   ( )
   thus contradicting the minimality of m . We thus get at least different elements ofm
   ( )2
   1 1 m
   C . Therefore, e ≥ = m ( m − 1) / 2 = [( m − ) − ] / 2, and solving for m gives the 2
   2 2 4
   desired result.
   A cell of a 2-configuration of a set A is a nonempty subset C of A such that 4
   i. for any two distinct elements a, b of C , there exists a sequence c , c , . . . , c of elements
   0 1 nof A with c = a, c = b , and such that { c , c } , { c , c } , . . . , { c , c } are all elements
   0 n 0 1 1 2 n − 1 nof the 2-configuration, andii. if a is an element of C and b is an element of A but not of C , there does NOTexist a sequence c , c , . . . , c of elements of A with c = a, c = b , and such that
   0 1 n 0 n
   { c , c } , { c , c } , . . . , { c , c } are all elements of the 2-configuration.
   0 1 1 2 n − 1 n
   Also, we define a 2-configuration of A to be barren if there is no subset { a , a , . . . , a } of A ,
   0 1 nwith n ≥ 2, such that { a , a } , { a , a } , . . . , { a , a } and { a , a } are all elements of the
   0 1 1 2 n − 1 n n 0
   2-configuration.