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: IMO 1983, Day 2, Problem 5
Tags: arithmetic sequence, Extremal combinatorics, Ramsey Theory, Arithmetic Progression, IMO, IMO 1983, combinatorics
28.12.2005 20:25
Hmm... strangely, I get a yes answer. Consider all numbers that consist only of $0$ and $1$, $\text{base 3}$. Due to not being equal, every 2 numbers must differ in at least one digit, so in a possible arithmetic sequence the third number would have a $2$ in that place. And since $1983<(12.10^{10}) _\text{base 2}$ while $100000>(12.10^{10})_\text{base 3}$, the first $1983$ such numbers are a valid sequence?
27.12.2011 17:12
Let $T_1$ be the set containing $\{ 1, 2, 4, 5 \} $ and if $T_n=\{ a_1, ..., a_k \}$ that $T_{n+1}=\{ a_1, ..., a_k, 2 \cdot a_k+a_1, 2 \cdot a_k +a_2, ..., 3a_k \}$. $T_{n+1}$ clearly doesn't contain three numbers forming arithmetic sequence. Let $f(n)$ be the greatest number in $T_n$. We see that ${|T_{n+1}|=2|T_n|}$ and $f(n+1)=3f(n)$. $|T_1|=4$ and $f(1)=5$ so $|T_{10}|=2048>1983$ and $f(7)=3645 \Rightarrow f(8)<11000 \Rightarrow f(10)<99000<10^5$ so we're done.
08.08.2018 21:06
2,1,4,3,6,5,8,7,...... the changes are -1,+3,-1,+3,... which ensures that an ap is not made
03.06.2020 00:25
I think this should work? I claim that it is possible. We start off with this solution using base $3$. Claim: If we put any three consecutive terms of an arithmetic sequence with positive difference in base $3$, there will be at least $1$ occurrence of each digit $0$, $1$, and $2$, in all of these numbers. To clarify: Let the first term be $1$ (mod $3$) and the common difference be $2$ (mod $3$), then the final digit of the $3$ numbers will be $1$ -> $0$ ->$2$ (in base $3$). The only case that contradicts this claim is if the difference is $0$, but these $3$ numbers will not be distinct. Thus, the minimal case, is if all the numbers in this sequence when written in base $3$, doesn't include a $2$. Now we want to know the $1983$rd digit of this sequence. Because each number in this sequence only contains $0$s and $1$s (in base $3$), we will want to know $1983$ in base $2$. $1983_{10}= 11110111111_{2}$ Lastly, the largest number in this sequence is the base $10$ representation of $11110111111_{3}$. This is just $87844$. So in the minimal case, $87844$ is the largest number in the sequence. Thus, the answer is $\boxed{Yes}$.
16.05.2021 15:03
Some more optimal constructions.
19.07.2023 14:09
solver2 wrote: 2,1,4,3,6,5,8,7,...... the changes are -1,+3,-1,+3,... which ensures that an ap is not made $\ 1,3,5$ is AP