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?
Problem
Source:
Tags: arithmetic sequence
25.05.2007 03:25
This is possible, we will construct such a set. Consider the set $S$ of natural numbers $a$ for which the representation of $a$ basis $3$ does not contain the digit $2$. Such a list doesn't contiain 3 terms in arithmetic progression: for all distinct $a,b\in S$, take $i$ the last position in which they differ. Then if $(a_i,b_i,c_i)$ is an arithmetic progression, the $i$-th digit must be $2$. The set $S\cap \{1,2,\ldots,10^5\}$ has more than 1983 elements, since $1983=(11110111111)_2$, while $(11110111111)_3=87844<10^5$.
19.03.2013 00:07
Let $\{a_{1},a_{2},...,a_{k}\}$ be a set of increasing positive integers no three of which are consecutive terms of an arithmetic progression then also the set $\{a_{1},a_{2},...,a_{k}\}\cup\{a_{1}+2a_{k}-a_{1},a_{2}+2a_{k}-a_{1},...,a_{k}+2a_{k}-a_{1}\}$ has the same property.This happens because $2a_{r}-a_{s}<a_{1}+2a_{k}-a_{1}$ and $2(a_{r}+2a_{k}-a_{1})-a_{s}>a_{k}+2a_{k}-a_{1}$ for $1\leq r$,$s\leq k$. Now if we start with the set $S_{1}=\{1,2,4,5\}$ then we take $S_{2}=S_{1}\cup\{10,11,13,14\}$, $S_{3}=S_{2}\cup\{28,29,31,32,37,38,40,41\}$ and so on.Denote $s_{n}$ the bigest element of $S_{n}$ then $s_{1}=5$ and $s_{n+1}=3s_{n}-1$ thus $s_{10}=88574<10^5$ and the cardinality of $S_{10}$ is $2048>1983$.