Competition problem — Combinatorics

Library / /290 of 377

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:
Let $S=\{s_{0}, \ldots, s_{n}\}$ be a finite set of integers, and define $S+k=\{s_{0}+k, \ldots, s_{n}+k\}$ . We say that $S$ and $T$ are equivalent, written $S \sim T$ , if $T=S+k$ for some $k$ . Given a (possibly infinite) set of integers $A$ , we say that $S$ tiles $A$ if $A$ can be partitioned into subsets equivalent to $S$ . Such a partition is called a tiling of $A$ by $S$ .

Find all sets $S$ with minimum element $1$ that tile $A=\{1, \ldots, 12\}$ .

Solution

Solution:
This can be done by brute force. Alternatively, note that if $P(x)$ and $Q(x)$ are polynomials with coefficients either $0$ or $1$ with $P(x) Q(x)=x+x^{2}+\cdots+x^{12}$ , then the set consisting of the exponents of nonzero terms in $P$ tiles $A$ . Either way, we find that $S$ is one of the following: $\{1\},\{1,2\},\{1,3\},\{1,4\},\{1,7\},\{1,2,3\}$ , $\{1,3,5\},\{1,5,9\},\{1,2,3,4\},\{1,2,7,8\},\{1,4,7,10\},\{1,2,3,4,5,6\},\{1,2,3,7,8,9\}$ , $\{1,2,5,6,9,10\},\{1,3,5,7,9,11\}$ , or $A$ itself.

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.