For each $n$ there exists $0\leq k(n)\leq 2001$ such that $n+k(n)=a_i$ for some $i$ Consider the following sequence $b_1=a_1$ $b_2=a_2$ $b_3=b_1+b_1b_2+r_3$ (where $r_3=k(b_1+b_1b_2)$) $b_4=b_1+b_1b_2+b_1b_2b_3 +r_4$ ( Where $r_4=k(b_1+b_1b_2+b_1b_2b_3)$) $b_{2005}=b_1+b_1b_2+b_1b_2b_3+...+b_1b_2b_3...b_{2005}+r_{2005}$ (where $r_{2005}=k(b_1+b_1b_2+b_1b_2b_3+...+b_1b_2b_3...b_{2005})$) Evidently$b_i$ is in the sequence $\{a_n\}$ in $r_3,r_4,...r_{2005}$ there exist two number $r_i=r_j$, ($i<j$) Of course $b_j-b_i=b_1b_2...b_i+b_1b_2...b_{i+1}+...+b_1b_2...b_j$ is divisible by $b_i$ Hence $b_j$ divisible by $b_i$

How do you get ideas like this one?

well, compliments, i suppose this is the fardest sequence problem to formalize i've ever seen

It is easy problem (I see solution for 5 sec), but it long to write. Idea is - exist N, suth that if finitely pairs $a_i|a_j, i\le N$, then density of sequense $a_i$ less than $O(N^{-s},s>0$. It give contradition with density not less 1/2001.

Ok, passing on the fact that $O(n^{-s})$ is nonsense (I guess you meant $O(n^{1-s})$), I must disagree with you about the difficulty of the problem, but since everything is relative, I would like to see your proof, because it would be really nice to see that the example of Erdos and Besicovith of a set of positive upper density with no two elements multiple of one another is wrong. Even if it's long, could you please post that proof? Only three lines in which one says the problem is simple, I'm afraid that won't suffice...

Ok! I am sorry for my English. Let $A=\{a_1<a_2<....\}$ set with terms $a_i$ We chose $b_1=a_1$ and finitly subset $A_1$,suth that $a_i \in A_1$ if and only if $b_1|a_i$. Then we chose minimal element $b_2\in A/A_1$ and finitly subset $A_2$, suth that $a_i \in A_2$ if and only if $b_2|a_i$, e.t.c construct $b_i,A_i$. If we have K pairs $a_i|a_j$, then subset $A_1UA_2U...A_k$ had only K terms (or less). Density all terms $a_i$, suth that $b_j\not|a_i$ is $(\prod_{j=1}^N (1-\frac{1}{b_j}) )^s$. It is long to prove about exist s (For it consider degree prime divisors $b_j$). Because $b_j$ is are $a_i$ exlution K terms, density $b_j$ is not less 1/2001. Therefore we have density $a_i$ less than $(\prod_{j=1}^N (1- \frac{1}{b_j}) )^s<N^{-s/2001}$. It give contradition.

thanks Rust .I see it is very interesting

Rust wrote: It is easy problem (I see solution for 5 sec), but it long to write. Idea is - exist N, suth that if finitely pairs $a_i|a_j, i\le N$, then density of sequense $a_i$ less than $O(N^{-s},s>0$. It give contradition with density not less 1/2001. What's $O(N^{-s},s>0$ ?

nmtruong1986 wrote: Hence $b_j$ divisible by $b_i$ How do you conclude $a_i|a_j$ or sth like that. For the solution of Rust, which basic concepts did you introduce, why can you conclude such things?

Lemma: There exist $x,y \in \mathbb {N}, x<y$ such that: $x|y , x+1|y+1 , x+2|y+2 , ... , x+2000|y+2000$ Proof is easy (Use this: $x+i$ must divide $y-x$) We name the pairs like (x,y) friends. Let $x_1 \in \mathbb {N}$ such that $x_1 \ge a_1$ Now we define: $X_1=\{x_1,x_1+1,x_1+2,...,x_1+2000\}$ $X_2=\{x_2,x_2+1,x_2+2,...,x_2+2000\}$ $X_3=\{x_3,x_3+1,x_3+2,...,x_3+2000\}$ . . . Such that $x_1,x_2,x_3,...$ are friends. We know that for all $i \in \mathbb {N}$ one of the members of $X_i$ is in $\{a_n\}$ So there exist infinitely $i,j,k \in \mathbb {N}, 0 \le k \le 2000 , i<j $ such that $x_i+k,x_j+k \in \{a_n\}$ and as $x_i+k|x_j+k$ so we're done

Soroush's solution is correct and the same as mine: to clarify, there exists an infinite sequence $x_1, x_2, \cdots$ such that $x_i+j|x_k+j$ for all $i<k$. We focus on constructing $x_{i+1}$ given $x_i$ by considering $x_{i+1}$ mod powers of $p$ for a fixed prime $p$ such that $p\mid \prod\limits_{j=0}^{2000} (x_i+j)$. Let $k$ such that $\nu_p(x_i+k)$ is maximal among $k=0,\cdots,2000$, call $t$. Then set $x_{i+1}\equiv -k(\bmod\; p^t)$ suffices mod $p$. This works because $\nu_p(x_i+m) = u (u\le t)$, then $x_{i+1}+m \equiv m-k(\bmod\; p^t)$. If $u<t$ then $\nu_p(m-k)=u$, and if $u=t$ then this also works because $p^t\mid m-k$. After finding $x_{i+1}$ mod each prime power, we can see that $x_{i+1}$ exists by Chinese Remainder Theorem. Now, let $f(n)$ be any number in $\{0,\cdots,2000\}$ such that $x_n+f(n)$ is in the sequence. By pigeonhole principle, there exists infinitely $m,n$ such that $f(m)=f(n)$. It follows that $x_m+f(m)\mid x_n+f(n)$ and both terms are in the sequence, so we are done.

Wait here is a much simpler way to construct $x_{i+1}$ based on $x_i$: Just do $x_{i+1}=x_i+ \prod\limits_{j=0}^{2000}(x_i+j)$

Consider $$\begin{matrix}b_1+1&b_1+2&\cdots &b_1+2001\\b_2+1&b_2+2&\cdots &b_2+2001\\\vdots&\vdots&\ddots&\vdots\end{matrix}$$where $b_1=a_1,b_{n+1}=(b_n+1)\cdots (b_n+2001)+b_n.$ Then each row there is at least one number in $\{a_n\}.$ By PHP there exists a column such that it includes infinite numbers in $\{a_n\}.$ Note that if $a<b$ are in same column, then $a\mid b,$ this ends the proof.$\Box$