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

英文解析

7. Show that, given any 2-configuration of a set A , every element of A belongs to exactlyone cell.
   Solution: First, given a , let C be the set of all b ∈ A for which there exists a sequenceaa = 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 = ba a 0 1 n
   ′ ′ ′ ′ ′ ′ ′
   and a = c , c , . . . , c = b , so the sequence b = c , c , . . . , c , c , c , . . . , c = b showsn n − 1 1 0
   0 1 m 1 mthat 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 .
   Thus, the second condition holds, and C is a cell. So a lies in at least one cell.aa
   But now, note that if C is a cell containing a , then all b for which such a sequencefrom a to b exists must lie in C (or the second condition is violated), and if no suchsequence exists, then b cannot lie in C (or the first condition is violated). Thus, theelements of C are uniquely determined, so there is exactly one cell containing a , andthe proof is complete.