HMMT 二月 2003 · 团队赛 · 第 7 题
HMMT February 2003 — Team Round — Problem 7
题目详情
- [20] Show that, given any 2-configuration of a set A , every element of A belongs to exactly one cell.
解析
- Show that, given any 2-configuration of a set A , every element of A belongs to exactly one cell. Solution: First, given a , let C be the set of all b ∈ A for which there exists a sequence a a = c , c , . . . , c = b as in the definition of a cell. Certainly a ∈ C (take n = 0); we 0 1 n a ′ claim that C is a cell. If b, b ∈ C , then there exist sequences a = c , c , . . . , c = b a a 0 1 n ′ ′ ′ ′ ′ ′ ′ and a = c , c , . . . , c = b , so the sequence b = c , c , . . . , c , c , c , . . . , c = b shows n n − 1 1 0 0 1 m 1 m that the first condition is met. For the second, suppose that there does exist a sequence ′ ′ b = c , c , . . . , c = b with b ∈ C , b ∈ / C . Then, concatenating with our sequence 0 1 n a a ′ ′ from a to b , we get a sequence from a to b , contradicting the assumption b ∈ / C . a Thus, the second condition holds, and C is a cell. So a lies in at least one cell. a But now, note that if C is a cell containing a , then all b for which such a sequence from a to b exists must lie in C (or the second condition is violated), and if no such sequence exists, then b cannot lie in C (or the first condition is violated). Thus, the elements of C are uniquely determined, so there is exactly one cell containing a , and the proof is complete.