HMMT 二月 2005 · TEAM2 赛 · 第 12 题

英文解析

12. [35] Let A be a finite set with more than one element. Prove that the number ofnonequivalent sets S which tile A is always even.
    Solution: Suppose A can be partitioned into sets S , . . . , S , each equivalent to S .
    0 m
    (This partition is unique, simply by choosing S to contain the smallest element of A ,
    S the smallest element of A not in S , etc.) Then if S = S + t , each element of A0
    1 0 j jcan be written uniquely as s + t for some i and j . But then the set T containing alli jt also tiles A by translation by the s . We cannot have S and T equivalent, for if so,
    j isince A has more than one element, both S and T would as well. This would implythat s + t = s + t , an overlap in the tiling of A . We can thus pair together S and
    0 1 1 0
    T , each of which tile A , so that the total number of sets tiling A must be even.