HMMT 二月 2005 · TEAM1 赛 · 第 15 题

HMMT February 2005 — TEAM1 Round — Problem 15

[35] Suppose S tiles N . Show that S is symmetric; that is, if − S = {− s , . . . , − s } , n 0 show that S ∼ − S . 2

解析

[35] Suppose S tiles N . Show that S is symmetric; that is, if − S = {− s , . . . , − s } , n 0 show that S ∼ − S . Solution: Assume without loss of generality that the minimum element of S is 0. By the previous problem, S tiles the set { 1 , 2 , . . . , k } for some positive integer k . Then let ∑ n s i P ( x ) be the polynomial x . To say that the set { 1 , 2 , . . . , k } , or equivalently the i =0 set { 0 , 1 , . . . , k − 1 } , is tiled by S is to say that there is some polynomial Q ( x ) with k − 1 k coefficients 0 or 1 such that P ( x ) Q ( x ) = 1 + x + · · · + x = ( x − 1) / ( x − 1). It follows that all the roots of P ( x ) are roots of unity, but P (1) 6 = 0. By question 11 above, this implies that P ( x ) is symmetric. Therefore, s + s = s + s = · · · = s + s , so S 0 n 1 n − 1 n 0 is symmetric. 6