Competition problem — Number theory

Library / /278 of 377

Number theory Difficulty 5.4 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$ .

Suppose that $S$ tiles the set of odd prime numbers. Prove that $S$ has only one element.

Solution

Solution:

Consider the set $S_{0}$ equivalent to $S$ that contains $3$ . If it contains $5$ but not $7$ , then the set $S_{1}$ equivalent to $S$ containing $7$ must contain $9$ , which is not prime. Likewise, $S_{0}$ cannot contain $7$ but not $5$ , because then the set $S_{1}$ containing $5$ must contain $9$ . Suppose $S_{0}$ contains $3, 5$ , and $7$ . Then any other set $S_{1}$ of the tiling contains elements $p, p+2$ , and $p+4$ . But not all of these can be prime, because one of them is divisible by $3$ . Finally, suppose $S_{0}$ contains $3$ and has second-smallest element $p>7$ . Then the set $S_{1}$ containing $5$ does not contain $7$ but does contain $p+2$ , and the set $S_{2}$ containing $7$ contains $p+4$ . But as before, not all of $p, p+2$ , and $p+4$ can be prime. Therefore $S$ has no second-smallest element, so it has only one element.

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.