HMMT 二月 2005 · TEAM1 赛 · 第 13 题

HMMT February 2005 — TEAM1 Round — Problem 13

[35] Let B be a set of integers either bounded below or bounded above. Then show that if S tiles all other integers Z \ B , then S tiles all integers Z .

解析

[35] Let B be a set of integers either bounded below or bounded above. Then show that 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 dif- ference between the largest and smallest element of S . Denote the sets in the partition of Z \ B by S , k ∈ Z , such that the minimum element of S , which we will denote c , k k k is strictly increasing as k increases. Since B is bounded above, there exists some k 0 such that c is larger than all the elements of B . Let k 0 ∞ ⋃ T = S . l k k = 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 is l l l c , T is completely determined by which of the integers c + 1 , c + 2 , . . . , c + a − 1 it l l l l l a − 1 contains. This implies that there are at most 2 possible nonequivalent sets T when l l ≥ k (here we extend the notion of equivalence to infinite sets in the natural way.) 0 By the Pigeonhole Principle, there must then be some l > l ≥ k such that T ∼ T . 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