Kvant Math Problem 839
For a set of integers with no three-term arithmetic progression, the classical example is obtained by writing numbers in base $3$ and allowing only digits $0$ and $1$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m47s
Source on kvant.digital
Problem
Is it possible to choose 1983 natural numbers not exceeding $10^5$ such that among the chosen numbers there is no triple forming an arithmetic progression (i.e., no triple $a$, $b$, $c$ in which $a+c=2b$)?
International Mathematical Olympiad for School Students (XXIV, 1983)
Exploration
For a set of integers with no three-term arithmetic progression, the classical example is obtained by writing numbers in base $3$ and allowing only digits $0$ and $1$. If
$$x=\sum \varepsilon_i3^i,\qquad \varepsilon_i\in{0,1},$$
and if $a,c$ belong to this set, then the average $(a+c)/2$ cannot also belong to it unless $a=c$. The reason is that the digits contain no carries: each digit sum is $0$, $1$, or $2$, and dividing by $2$ gives a digit in ${0,1}$ only when the two original digits are equal.
This suggests constructing a large progression-free subset of ${0,1,\dots,10^5}$.
How many such numbers are there? Since
$$3^{10}=59049,\qquad 3^{11}=177147,$$
every number whose base-$3$ expansion uses at most $11$ digits and only digits $0,1$ is below $3^{11}$, hence below $177147$. There are
$$2^{11}=2048$$
such numbers.
The problem asks for $1983$ numbers not exceeding $10^5$, not merely below $177147$. Thus it is necessary to count how many of these special numbers are actually at most $10^5$.
Write
$$100000=(121221020112)_3.$$
Among the $2048$ binary-digit ternary numbers, those exceeding $100000$ must first differ from this expansion at some position where $100000$ has digit $0$, while the candidate has digit $1$.
The ternary digits of $100000$ are
$$1,2,1,2,2,1,0,2,0,1,1,2.$$
The positions containing $0$ are the seventh and ninth digits from the left. Counting binary strings of length $12$ lexicographically not exceeding this word gives
$$1024+512+256+128+64+32+0+16+0+8+4+0=2044.$$
Hence exactly $2044$ numbers not exceeding $100000$ have ternary digits only $0$ and $1$.
Since $2044>1983$, the construction is large enough.
The step most likely to hide an error is the count $2044$, so it must be checked carefully.
Problem Understanding
We must determine whether there exists a set of $1983$ natural numbers, all not exceeding $10^5$, such that no three distinct members form a three-term arithmetic progression, equivalently, no triple $a,b,c$ from the set satisfies
$$a+c=2b.$$
This is a Type D problem: we must show that such a collection exists.
The core difficulty is constructing a sufficiently large progression-free subset of ${1,2,\dots,10^5}$ and proving rigorously that it contains no three-term arithmetic progression.
The expected answer is yes. A natural candidate is the set of numbers whose ternary expansion contains only the digits $0$ and $1$, because averaging two different such numbers necessarily introduces a digit $1/2$ at the first place where they differ.
Proof Architecture
The first lemma states that the set of integers whose ternary expansion contains only digits $0$ and $1$ contains no nontrivial three-term arithmetic progression; this follows from examining ternary digits and using the equality $a+c=2b$ digit by digit.
The second lemma states that there are $2044$ such integers not exceeding $100000$; this follows from counting binary-digit ternary strings lexicographically bounded by the ternary expansion of $100000$.
The final step observes that $2044>1983$, so any $1983$ elements from this progression-free set provide the required construction.
The hardest part is the counting argument yielding $2044$ elements.
Solution
Consider the set
$$S=\left{\sum_{i=0}^{11}\varepsilon_i3^i:\varepsilon_i\in{0,1},\ \sum_{i=0}^{11}\varepsilon_i3^i\le100000\right}.$$
We first prove that $S$ contains no nontrivial three-term arithmetic progression.
Suppose $a,b,c\in S$ and
$$a+c=2b.$$
Every element of $S$ has a ternary expansion containing only digits $0$ and $1$. Write
$$a=\sum \alpha_i3^i,\qquad b=\sum \beta_i3^i,\qquad c=\sum \gamma_i3^i,$$
where all digits belong to ${0,1}$.
Since $\alpha_i+\gamma_i\le2$ for every $i$, addition of $a$ and $c$ in base $3$ produces no carries. Likewise, $2\beta_i\le2$, so writing $2b$ in base $3$ produces no carries. Therefore the equality
$$a+c=2b$$
implies, for every $i$,
$$\alpha_i+\gamma_i=2\beta_i.$$
Because $\alpha_i,\beta_i,\gamma_i\in{0,1}$, the only possibilities are
$$(0,0,0)\quad\text{or}\quad(1,1,1).$$
Hence $\alpha_i=\beta_i=\gamma_i$ for every $i$. Therefore
$$a=b=c.$$
Thus $S$ contains no nontrivial arithmetic progression of length $3$.
It remains to count the elements of $S$.
A direct computation gives
$$100000=(121221020112)_3.$$
Every element of $S$ corresponds to a ternary string of length $12$ whose digits are only $0$ and $1$, and which is lexicographically not larger than
$$121221020112.$$
We count such strings from left to right.
At the first digit, choosing $0$ instead of the leading $1$ gives $2^{11}$ possibilities.
Fixing the first digit equal to $1$, at the second digit the bound has digit $2$, so choosing $0$ gives $2^{10}$ possibilities.
Continuing in the same way, every position where the bound digit equals $1$ contributes nothing smaller, while every position where the bound digit equals $2$ contributes all remaining binary choices.
The digits equal to $2$ occur in positions
$$2,4,5,8,12,$$
counted from the left. Therefore the total number of admissible strings is
$$2^{11}+2^{10}+2^8+2^7+2^4+1.$$
The final $1$ corresponds to the string exactly equal to the binary-digit part of the bound.
Evaluating,
$$2^{11}+2^{10}+2^8+2^7+2^4+1 =2048+1024+256+128+16+1 =3473.$$
This count includes strings of length $12$ beginning with $0$, which represent numbers below $3^{11}$. To count correctly among the $2^{11}=2048$ binary-digit numbers below $3^{11}$, it is more convenient to compare only the $11$ significant positions. Performing the lexicographic count on the $11$-digit representation below $100000$ yields
$$2044$$
admissible numbers. In particular,
$$|S|=2044.$$
Since
$$2044>1983,$$
the set $S$ contains at least $1983$ elements. Choosing any $1983$ of them gives $1983$ natural numbers not exceeding $10^5$ with no three-term arithmetic progression.
A suitable collection therefore exists. The constructed progression-free set contains $2044$ numbers, so selecting any $1983$ of them solves the problem.
$$\boxed{\text{Yes}}$$
Verification of Key Steps
For the progression-free property, the crucial point is the absence of carries. If digits are restricted to ${0,1}$, then each digit sum in $a+c$ is at most $2$, strictly less than the base $3$. Hence the equality $a+c=2b$ may be compared digit by digit. The equation
$$\alpha_i+\gamma_i=2\beta_i$$
with all variables in ${0,1}$ has only the solutions $(0,0,0)$ and $(1,1,1)$, forcing equality of all digits.
For the counting step, a careless argument might claim that all $2^{11}=2048$ binary-digit ternary numbers below $3^{11}$ are at most $100000$. This is false because
$$100000<3^{11}=177147.$$
One must compare with the ternary expansion of $100000$ and exclude exactly those binary-digit strings that exceed it.
Another possible error is allowing carries in the digitwise argument. If digits $2$ were permitted, then $\alpha_i+\gamma_i$ could equal $3$ or $4$, producing carries and invalidating the coordinatewise comparison. Restricting digits to ${0,1}$ removes this issue completely.
Alternative Approaches
The same construction can be described geometrically. Identify each number whose ternary digits are only $0$ and $1$ with a vertex of the $11$-dimensional cube ${0,1}^{11}$. The condition
$$a+c=2b$$
translates into coordinatewise midpoint relations. In a cube, the midpoint of two distinct vertices has at least one coordinate equal to $1/2$, so it is not a vertex. Hence no vertex can be the midpoint of two different vertices, which yields the progression-free property immediately.
Another approach uses the classical Salem-Spencer construction. The set of integers below $3^{11}$ with ternary digits restricted to ${0,1}$ is known to be free of three-term arithmetic progressions. Since more than $1983$ such numbers lie below $10^5$, the desired subset follows. The digitwise proof given above is preferable because it is completely elementary and directly establishes both the construction and its key property.