Maths Olympiad Prep

Library / /81 of 377

Combinatorics Difficulty 4.7 AIME Prove it United States

Problem:
Suppose SS tiles N\mathbb{N}. Show that SS is symmetric; that is, if S={sn,,s0}-S=\{-s_{n}, \ldots,-s_{0}\}, show that SSS \sim -S.

Solution

Solution:
Assume without loss of generality that the minimum element of SS is 00. By the previous problem, SS tiles the set {1,2,,k}\{1,2, \ldots, k\} for some positive integer kk. Then let P(x)P(x) be the polynomial i=0nxsi\sum_{i=0}^{n} x^{s_{i}}. To say that the set {1,2,,k}\{1,2, \ldots, k\}, or equivalently the set {0,1,,k1}\{0,1, \ldots, k-1\}, is tiled by SS is to say that there is some polynomial Q(x)Q(x) with coefficients 00 or 11 such that P(x)Q(x)=1+x++xk1=xk1x1P(x) Q(x) = 1 + x + \cdots + x^{k-1} = \frac{x^{k}-1}{x-1}. It follows that all the roots of P(x)P(x) are roots of unity, but P(1)0P(1) \neq 0. By question 11 above, this implies that P(x)P(x) is symmetric. Therefore, s0+sn=s1+sn1==sn+s0s_{0} + s_{n} = s_{1} + s_{n-1} = \cdots = s_{n} + s_{0}, so SS is symmetric.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.