HMMT 二月 2005 · TEAM2 赛 · 第 12 题

HMMT February 2005 — TEAM2 Round — Problem 12

[35] Let A be a finite set with more than one element. Prove that the number of nonequivalent sets S which tile A is always even.

解析

[35] Let A be a finite set with more than one element. Prove that the number of nonequivalent 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 , 0 S the smallest element of A not in S , etc.) Then if S = S + t , each element of A 1 0 j j can be written uniquely as s + t for some i and j . But then the set T containing all i j t also tiles A by translation by the s . We cannot have S and T equivalent, for if so, j i since A has more than one element, both S and T would as well. This would imply that 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.