We call a set $A\subset \mathbb{R}$ free of arithmetic progressions if for all distinct $a,b,c\in A$ we have $a+b\neq 2c.$ Prove that the set $\{0,1,2,\ldots 3^8-1\}$ has a subset $A$ which is free of arithmetic progressions and has at least $256$ elements.
Problem
Source: Romania JBMO TST 2022
Tags: combinatorics, Romanian TST
MathSaiyan
21.04.2022 00:51
Change that $8$ to an $n$ and use induction to prove that we can find a free $A \subset \{0,1,\ldots,3^n-1\}$ with $\vert A \vert = 2^n$. Let $A_n$ be some free subset of $\{0,1,\ldots,3^n-1\}$ with $2^n$ elements. Then $A_{n+1}$ is just $A\cup (A+2\cdot 3^{n-1})$. Basically clone $A_n$ for $\{0,1,\ldots,3^n-1\}$, $\{3^n,\ldots,2\cdot 3^n-1\}$ and $\{2\cdot 3^n,\ldots,3^{n+1}-1\}$ and eliminate the $A_n$ in the middle. It's rather easy to prove this works.
PROA200
21.04.2022 04:13
The $256$ is just a dead giveaway...
All ternary numbers in $\{0, 1, 2,\ldots, 3^8-1\}$ not containing the digit $2$.
For any $c$, $2c$ contains only the digits $0$ and $2$ when expressed in ternary. Since no carries can occur when adding $a$ and $b$, and $a$ and $b$ contain only the digits $0$ and $1$, we force each $2$ in the ternary representation of $2c$ to correspond to a $1$ in both $a$ and $b$, so $a=b=c$, contradiction.
dgrozev
21.04.2022 15:24
The construction used above is well known and due to Erdos and Turan, I think. A similar problem, with the same idea, was IMO 1983, p5. A more sophisticated one with better lower bound was given at a Bulgarian TST 2012 (p6). Some history and other comments can be seen here.