HMMT 二月 2005 · TEAM1 赛 · 第 13 题

英文解析

13. [35] Let B be a set of integers either bounded below or bounded above. Then showthat if S tiles all other integers Z \ B , then S tiles all integers Z .
    Solution: Assume B is bounded above; the other case is analogous. Let a be the difference between the largest and smallest element of S . Denote the sets in the partitionof Z \ B by S , k ∈ Z , such that the minimum element of S , which we will denote c ,
    k k kis strictly increasing as k increases. Since B is bounded above, there exists some ksuch that c is larger than all the elements of B . Let 0
    0 k
    ∞
    ⋃
    T = S .
    l kk = l
    Suppose l ≥ k . Note that any element in S , k < l , is at most c − 1 + a . Therefore,
    0 k l
    T contains all integers that are at least c + a . Since the minimum element of T isl l lc , T is completely determined by which of the integers c + 1 , c + 2 , . . . , c + a − 1 itl l l l la − 1
    contains. This implies that there are at most 2 possible nonequivalent sets T whenll ≥ k (here we extend the notion of equivalence to infinite sets in the natural way.)
    By the Pigeonhole Principle, there must then be some l > l ≥ k such that T ∼ T .0
    2 1 0 l l
    1 2
    But then it is easy to see that the set S ∪ S ∪ · · · ∪ S tiles Z , so S tiles Z .
    l l +1 l − 1
    1 1 2 5