This seems much too easy, so I am doubting myself. Label an integer bad if it cannot be picked to be a further element in the sequence $a_i$. I claim that for $s \ge 1$, $a_{t+s} \le a_t+\frac{(t+s-1)(t+s-2)}{2}+s$. To prove this, simply look at how many bad values we have accumulated so far. So initially, we start with at most $a_t+\frac{t(t-1)}{2}$ bad values, the numbers $1$ through $a_t$, and the numbers $2a_j-a_i$ for $j > i$, since $a_i, a_j, 2a_j-a_i$ would form a progression. Note that when we add a new element to our sequence, every integer less than it is bad (elements already in our sequence become bad). So look at choosing the element $a_{t+s}$. We will have at most $a_t + (s-1) + \frac{(t+s-1)(t+s-2)}{2}$ bad numbers (from the initial integers, new chosen integers, and arithmetic progressions). Therefore, since all numbers under $a_{t+s}$ must be bad $a_{t+s} \le a_t + (s-1) + \frac{(t+s-1)(t+s-2)}{2}+1$ as claimed. It's easy to see that now $a_{t+s} \le C(t+s)^2$ for any $1/2 < C < 1$ for large enough $s$ and $t$. This trivially implies the result. (Since $\sqrt{1/C} > 1$)

i think it is correct.

Let us denote $A=\{a_i\mid i\in\mathbb{N}\}$. The mere construction of $a_i$ implies the following property, which is crucial for obtaining the desired estimate. (i) For any $ n\in\mathbb{N}\,,\, n>a_t\,,\, n\not\in A $, there exist $a_i,a_j\in A\,,\, a_i<a_j<n $ such that $a_i,a_j,n $ form an arithmetic progression. Using (i) we get: \[\text{(ii)}\,\,\,\,\,\, A(x)(A(x)-1)/2 +a_t +A(x)+1\ge x \] We will prove that for any $\varepsilon >0$ it holds $A(x)\ge (\sqrt{2}-\varepsilon) \sqrt{x}$, for sufficiantly big $x$. Assume on the contrary it is not true. Then there exist $x_1<x_2<\ldots$ with $\lim x_n=\infty$ and $A(x_n)<(\sqrt{2}-\varepsilon) \sqrt{x_n}\,,\, n=1,2,\ldots$. Plugging $x_n$ into (ii) and letting $n\to \infty$ we get a contradiction.

mathocean97 wrote: So look at choosing the element $a_{t+s}$. We will have at most $a_t + (s-1) + \frac{(t+s-1)(t+s-2)}{2}$ bad numbers (from the initial integers, new chosen integers, and arithmetic progressions). Therefore, since all numbers under $a_{t+s}$ must be bad $a_{t+s} \le a_t + (s-1) + \frac{(t+s-1)(t+s-2)}{2}+1$ as claimed. I think it's not true, we choose $a_{t+s}$ after choosing $a_{t+1}, a_{t+2},\ldots, a_{t+s-1}$, so bad numbers for t+s more than $a_t + (s-1) + \frac{(t+s-1)(t+s-2)}{2}$, for example 1 integer between $a_{t+1}$ and $a_{t+2}$ can be bad number I think $a_{t+s}\le a_t+C^2_t+C^2_{t+1}+\cdots+C^2_{t+s-1}+s$

Am I wrong here? Let $A=a_t$. So let's say we have declared who $a_1,...,a_k$ are, and we want to declare $a_{k+1}$. There are at most ${{k}\choose{2}}+k \simeq k^2/2$ "forbidden" values, namely $a_1,...,a_k$ and $2a_j-a_i$ for all $1 \le i<j \le k$. Let's add $1,2,...,A$ to the list of forbidden values, so there are still at most $ \simeq k^2/2$ forbidden values. Then take the first value that isn't forbidden, $b$. Clearly $b \le \simeq k^2/2$ If $a_{k+1}$ can take this value $b$, then we're done, since eventually $a_n \simeq n^2/2$ (and we actually get $c=\sqrt{2}-\epsilon$). Otherwise, $a_{k+1}$ can't be assigned the value $b$ because there exist $A \le a_{\ell}<b<a_{\ell+1}$. The question is, why wasn't $a_{\ell+1}$ assigned the value of $b$? It should have been! So we're done.

Randomly mocked this China TST Day, seems a bit too easy for a China TST 2 but I enjoy these sorts of problems with short global solutions. Same solution as many above. Let $B_k = \{2a_i-a_j | 1 \leq i \leq j \leq k\}$.

$\textbf{Main Lemma:}$ There exist some fixed $a \in \mathbb{N}$ and $N_0 \in \mathbb{N}$ such that each $a+1 \leq i \leq a_{k+1}$ is an element of $B_k$ for all $k \geq N_0$. $\textbf{Proof)}$ As explained in the $\textbf{Motivation}$ section, we can see that for all $m \geq t$, $B_m$ will contain each of the numbers $a_t, \cdots, a_{m+1}-1$. This is because, we know that for $l \geq t$, $a_{l+1}$ is the smallest positive integer greater than $a_l$ that is not part of an arithmetic progression containing elements of ${a_i}_{i \geq 1}$, that means that for each $M \geq a_t$, $M \neq a_j$ for $j \in \mathbb{N}$, there exists some pair $i < j$ such that $2a_i-a_j = M$, moreover, we have allowed $i = j$ in the definition of $B_k$ meaning that $a_i \in B_k$ for all $1 \leq i \leq m$. Thus, taking $a = a_t+1$ proves the lemma. $\blacksquare$ Then for $m \geq N_0$, notice that $$\frac{m(m+1)}{2} = {m \choose 2}+m \geq |B_k| \geq a_{m+1}-1-a_t = a_{m+1}-a$$ Taking $m \to m+1$, we have that $$\frac{m^2}{2} \geq \frac{m(m-1)}{2}+a \geq a_{m}$$for all sufficiently large $m \in \mathbb{N}$. Thus, there are going to be at least $f(x) = \lfloor \sqrt{2x} \rfloor$ integers in the sequence $a_1, \cdots, a_{f(x)} \leq x$, in particular for all $c = 2-\varepsilon$, $A(x) \geq f(x) \geq c\sqrt{x}$ finishes the proof by taking $\varepsilon \in (0, \sqrt{2}-1)$. $\blacksquare$ $\blacksquare$ Having solved the problem, which is relatively weak in only requiring $c > 1$, as any positive real less than $\sqrt{2}$ simply works, it may be a good idea to investigate, whether it is true that $A(x) \geq \sqrt{2x}$ for all sufficiently large $x$, I have not thought about it myself so it may or may not be obvious.