Putnam 2012, Problem A-4

Let $q$ and $r$ be integers with $q > 0$, and let $A$ and $B$ be intervals on the real line. Let $T$ be the set of all $b + mq$ where $b$ and $m$ are integers with $b$ in $B$, and let $S$ be the set of all integers $a$ in $A$ such that $ra$ is in $T$. Show that if the product of the lengths of $A$ and $B$ is less than $q$, then $S$ is the intersection of $A$ with some arithmetic progression.

Solution:
We begin with an easy lemma.

**Lemma.** Let $S$ be a finite set of integers with the following property: for all $a,b,c \in S$ with $a \leq b \leq c$, we also have $a + c - b \in S$. Then $S$ is an arithmetic progression.

**Proof.** We may assume $\#S \geq 3$, as otherwise $S$ is trivially an arithmetic progression. Let $a_1, a_2$ be the smallest and second-smallest elements of $S$, respectively, and put $d = a_2 - a_1$. Let $m$ be the smallest positive integer such that $a_1 + md \notin S$. Suppose that there exists an integer $n$ contained in $S$ but not in $\{a_1, a_1 + d, \ldots, a_1 + (m-1)d\}$, and choose the least such $n$. By the hypothesis applied with $(a,b,c) = (a_1, a_2, n)$, we see that $n-d$ also has the property, a contradiction.

We now return to the original problem. By dividing $B,q,r$ by $\gcd(q,r)$ if necessary, we may reduce to the case where $\gcd(q,r) = 1$. We may assume $\#S \geq 3$, as otherwise $S$ is trivially an arithmetic progression. Let $a_1, a_2, a_3$ be any three distinct elements of $S$, labeled so that $a_1 < a_2 < a_3$, and write $ra_i = b_i + m_iq$ with $b_i, m_i \in \mathbb{Z}$ and $b_i \in B$. Note that $b_1, b_2, b_3$ must also be distinct, so the differences $b_2 - b_1, b_3 - b_1, b_3 - b_2$ are all nonzero; consequently, two of them have the same sign. If $b_i - b_j$ and $b_k - b_l$ have the same sign, then we must have
$$(a_i - a_j)(b_k - b_l) = (b_i - b_j)(a_k - a_l)$$
because both sides are of the same sign, of absolute value less than $q$, and congruent to each other modulo $q$. In other words, the points $(a_1, b_1), (a_2, b_2), (a_3, b_3)$ in $\mathbb{R}^2$ are collinear. It follows that $a_4 = a_1 + a_3 - a_2$ also belongs to $S$ (by taking $b_4 = b_1 + b_3 - b_2$), so $S$ satisfies the conditions of the lemma. It is therefore an arithmetic progression.

**Reinterpretations.** One can also interpret this argument geometrically using cross products (suggested by Noam Elkies), or directly in terms of congruences (suggested by Karl Mahlburg).

**Remark.** The problem phrasing is somewhat confusing: to say that "$S$ is the intersection of [the interval] $A$ with an arithmetic progression" is the same thing as saying that "$S$ is the empty set or an arithmetic progression" unless it is implied that arithmetic progressions are necessarily infinite. Under that interpretation, however, the problem becomes false; for instance, for
$$q = 5, r = 1, A = [1,3], B = [0,2],$$
we have
$$T = \{\cdots, 0, 1, 2, 5, 6, 7, \ldots\}, S = \{1,2\}.$$