HMMT 二月 2003 · 团队赛 · 第 6 题
HMMT February 2003 — Team Round — Problem 6
题目详情
- [40] Prove that any 2-configuration containing e elements is m -separable for some √ 1 1 m ≤ + 2 e + . 2 4 A cell of a 2-configuration of a set A is a nonempty subset C of A such that i. for any two distinct elements a, b of C , there exists a sequence c , c , . . . , c of elements 0 1 n of 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 n of the 2-configuration, and ii. if a is an element of C and b is an element of A but not of C , there does NOT exist 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 n with 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.
解析
- 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 on set A is m -separable, and fix a corresponding labeling of the elements of A . Let A be i the set of all elements with the label i . Then, for any i, j with 1 ≤ i < j ≤ m , there must exist a ∈ A , a ∈ A with { a , a } ∈ C , since otherwise the elements of A could i i j j i j j have been reassigned the label i , decreasing the number of distinct labels necessary and ( ) m thus contradicting the minimality of m . We thus get at least different elements of 2 ( ) m 1 1 2 C . Therefore, e ≥ = m ( m − 1) / 2 = [( m − ) − ] / 2, and solving for m gives the 2 2 4 desired result. 4 A cell of a 2-configuration of a set A is a nonempty subset C of A such that i. for any two distinct elements a, b of C , there exists a sequence c , c , . . . , c of elements 0 1 n of 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 n of the 2-configuration, and ii. if a is an element of C and b is an element of A but not of C , there does NOT exist 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 n with 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.