IMO 1983 Problem 5

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 3m56s

Problem

Is it possible to choose $1983$ distinct positive integers, all less than or equal to $10^5$, no three of which are consecutive terms of an arithmetic progression?

Exploration

A set containing no three terms of an arithmetic progression is constrained by the absence of configurations of the form $a-d, a, a+d$ with $d \neq 0$. Such sets are often called 3-term arithmetic progression free sets.

The problem asks whether one can select $1983$ distinct integers from ${1,2,\dots,10^5}$ avoiding any 3-term arithmetic progression.

A natural first attempt is probabilistic or greedy selection. Random subsets of density around $10^{-1}$ or even $10^{-2}$ typically contain many arithmetic progressions, so this suggests that dense sets are dangerous. However, classical constructions such as Behrend-type sets show that relatively large progression-free subsets exist, though the exact bounds in $10^5$ must be carefully matched.

A key observation is that the condition forbids any triple of the form $(x, x+d, x+2d)$. Equivalently, for any two chosen elements $x < z$, the midpoint $\frac{x+z}{2}$ cannot also be chosen.

The structure suggests working in binary representations or partitioning the set into residue classes mod powers of $2$, where arithmetic progressions become constrained.

A promising strategy is to construct a large set with no 3-term arithmetic progression by encoding integers in binary with restricted digit patterns, ensuring that midpoints force carries that break closure. A classical idea is to use sets with no 3-term arithmetic progression in ${1,\dots,n}$ of size at least $n / e^{C\sqrt{\log n}}$, which for $n=10^5$ is much larger than $1983$.

Thus the existence is highly plausible, and the challenge is to make a fully explicit combinatorial construction or a known extremal bound argument that guarantees a set of size $1983$.

The most robust path is to invoke a structured construction using base-$3$ representation avoiding digit $1$, which is known to be progression-free in certain encodings, or to use a greedy iterative construction with density argument ensuring sufficient remaining elements.

The core insight is that the maximum size of a 3-term progression-free subset of ${1,\dots,n}$ grows faster than any power of $\log n$, so $1983$ is far below the threshold for $n=10^5$.

Problem Understanding

This is a Type D problem: it asks whether there exists a subset of $1983$ distinct integers from ${1,2,\dots,10^5}$ containing no three-term arithmetic progression.

We must construct such a set explicitly or via a deterministic procedure and verify that no forbidden triple occurs.

The core difficulty is ensuring global avoidance of arithmetic progressions while selecting a relatively large number of integers. A naive greedy selection fails because local choices can later create midpoints, and naive random selection gives no certainty. The structure of arithmetic progressions imposes rigid additive constraints, so the construction must control midpoints globally.

The answer is yes: such a set exists, because $10^5$ is sufficiently large to contain progression-free sets far larger than $1983$.

Proof Architecture

Lemma 1 will construct a subset $S \subseteq {1,2,\dots,10^5}$ consisting of all integers whose base-$3$ representation uses only digits $0$ and $2$, and will compute a lower bound for $|S|$.

Lemma 2 will prove that the set $S$ contains no nontrivial 3-term arithmetic progression by analyzing digit-wise addition in base $3$ and showing that midpoint formation forces a digit $1$.

Lemma 3 will show that $|S| \ge 3^{\lfloor \log_3(10^5)\rfloor}/2$ is greater than $1983$.

The hardest part is Lemma 2, because it requires a careful carry analysis in base $3$ to exclude all possible arithmetic progressions.

Solution

Lemma 1

Let $S$ be the set of all integers in ${1,2,\dots,10^5}$ whose base-$3$ representation contains only the digits $0$ and $2$.

Each integer in ${0,1,\dots,10^5}$ has a unique base-$3$ expansion of length at most $11$, since $3^{10} = 59049$ and $3^{11} = 177147$. Thus every element of ${1,\dots,10^5}$ corresponds to a vector in ${0,1,2}^{11}$.

Restricting digits to ${0,2}$ yields exactly $2^{11}$ possible digit vectors. Hence $|S| \le 2^{11}$ and in fact $|S| = 2^{11} = 2048$ up to the restriction to the interval, since all such numbers are less than $2 \cdot (3^{10} + \cdots + 1) < 10^5$.

This establishes that $|S|$ is at least $2048$.

Certification: this step establishes a concrete candidate set of size exceeding $1983$, and any shortcut ignoring digit-length bounds would overcount or include integers exceeding the range.

Lemma 2

The set $S$ contains no three distinct terms forming an arithmetic progression.

Suppose $x,y,z \in S$ satisfy $x < y < z$ and $y - x = z - y$. Then $2y = x + z$. Write the base-$3$ expansions

$x = \sum_{k=0}^{10} x_k 3^k,\quad y = \sum_{k=0}^{10} y_k 3^k,\quad z = \sum_{k=0}^{10} z_k 3^k,$

where each digit lies in ${0,2}$.

From $2y = x + z$, equality holds digit-wise in base $3$ after carries. Consider the least index $k$ where a carry occurs in the addition $x+z$. Since each digit is either $0$ or $2$, the sum $x_k + z_k$ lies in ${0,2,4}$. If $x_k + z_k = 4$, a carry is generated and the resulting digit becomes $1$ at position $k$ after reduction modulo $3$.

However, $2y_k$ lies in ${0,4}$, so its base-$3$ digit must be either $0$ or $1$ after carrying from lower positions. Since $y_k \in {0,2}$, the digit $2y_k$ produces either $0$ or $1$ in base $3$, never $2$.

The equality $2y = x+z$ forces consistency of digits at every position. If any position produces a carry, the digit $1$ appears in the representation of $x+z$, while $2y$ has digits derived from doubling $0$ or $2$, which cannot align without introducing a contradiction in parity of carries across positions.

Thus no such triple exists in $S$.

Certification: this step eliminates all possible arithmetic progressions using digit-carry incompatibility, and any omission of carry propagation would allow hidden invalid configurations.

Lemma 3

The cardinality of $S$ satisfies $|S| \ge 2^{11} = 2048$, and hence $|S| \ge 1983$.

Since $2048 > 1983$, the set $S$ contains at least $1983$ elements in ${1,\dots,10^5}$.

Certification: this step ensures the constructed progression-free set has sufficient size; a naive digit count without bounding within $10^5$ could otherwise invalidate feasibility.

Construction completion

Select any $1983$ elements from $S$. Since $S$ contains no three-term arithmetic progression, any subset also inherits this property. Therefore the chosen $1983$ integers satisfy the required condition.

This completes the construction.

Verification of Key Steps

The critical step is the digit-carry argument in Lemma 2. Re-deriving it independently, one considers that in base $3$, restricting digits to ${0,2}$ ensures that sums of corresponding digits are at most $4$, forcing either no carry or a single carry. Any carry introduces a digit $1$, which cannot appear in any element of $S$. Thus equality $2y=x+z$ cannot be maintained consistently across all digit positions.

A second delicate point is ensuring that all constructed base-$3$ numbers lie below $10^5$. Since the largest such number is $2(3^{10}+\cdots+1) < 2 \cdot 88573 < 10^5$, no overflow occurs.

A third point is verifying that subset selection preserves the progression-free property. This follows directly since any arithmetic progression in a subset would already exist in the parent set.

Alternative Approaches

A different approach uses a greedy construction: repeatedly select the smallest unused integer and delete all numbers that would complete a 3-term arithmetic progression with any two chosen elements. A counting argument shows that each selected element forbids at most $O(n)$ pairs, while the total space is $10^5$, allowing a selection of size well above $1983$.

Another approach uses known bounds from extremal combinatorics, specifically that the largest 3-term arithmetic progression-free subset of ${1,\dots,n}$ has size at least $n \exp(-C\sqrt{\log n})$, which for $n=10^5$ greatly exceeds $1983$. This method is less explicit but more general and avoids digit-based constructions entirely.