Rijul saini wrote: Indian Postal Training Set 6, Problem 1 Does there exist an increasing sequence of positive integers $a_1 , a_2 ,\cdots$ with the following two properties? (i) Every positive integer $n$ can be uniquely expressed in the form $n = a_j - a_i$ , (ii) $\frac{a_k}{k^3}$ is bounded. See problem here and here But no solution

Ovchinnikov Denis wrote: Rijul saini wrote: Indian Postal Training Set 6, Problem 1 Does there exist an increasing sequence of positive integers $a_1 , a_2 ,\cdots$ with the following two properties? (i) Every positive integer $n$ can be uniquely expressed in the form $n = a_j - a_i$ , (ii) $\frac{a_k}{k^3}$ is bounded. See problem here and here But no solution Yeah, I heard it was proposed by Paul Erdos himself

Let $a_{2n}=(2n)^3$ and $a_{2n+1}=a_{2n}+h$, were $h$ is minimal natural number, suth that $a_i-a_j=h, j<i\le {2n}$ had not solution. Obviosly $h\le \frac{2n(2n-1)}{2}$, therefore $a_{2n+1}<(2n+1)^3.$

Rust wrote: Let $a_{2n}=(2n)^3$ and $a_{2n+1}=a_{2n}+h$, were $h$ is minimal natural number, suth that $a_i-a_j=h, j<i\le {2n}$ had not solution. Obviosly $h\le \frac{2n(2n-1)}{2}$, therefore $a_{2n+1}<(2n+1)^3.$ Could you explain this in more detail?

My solution is not correct. We must choose any $a_{n+1}$. These way is correct for $a_{2n}=2^{2n}$. But in these case $a_n\not = O(n^3).$

I like this problem very much, that's why I shall post a solution which I know. We shall prove that there exists such sequence. Such sequence will be constructed by induction. Let $a_1=1$ and $a_2=2$. We assume that $S=\{a_1,\ldots,a_n\}$ are increasing so that $a_j<j^3$ for all $j=1,\ldots,n$ and all the differences $a_i-a_j$ are pairwise distinct. Let $m$ be the smallest positive integer number which is not of the form $a_i-a_j$. Since there are at most $\binom{n}{2}<n^2$ such a difference, so $m<n^2$. Let $x$ be a good number if both $x$ and $x+m$ are not of the form $a_i-a_j+a_k$. Since there are at most $2\binom{n}3=\frac{n(n-1)(n-2)}{3}< n^3$ such "bad number". So if $a_{n+1}$ be the smallest good number then $a_{n+1}\leq n^3$. Now if there is some $1\leq j\leq n$ such that $a_{n+1}-a_j=m$ then $m$ has been chosen in the next step. If not, we just put $a_{n+2}=a_{n+1}+m$ then $a_{n+2}<n^3+n^2<(n+1)^3$ and in the next step $m$ has been chosen. So we are done.

pluricomplex wrote: I like this problem very much, that's why I shall post a solution which I know. We shall prove that there exists such sequence. Such sequence will be constructed by induction. Let $a_1=1$ and $a_2=2$. We assume that $S=\{a_1,\ldots,a_n\}$ are increasing so that $a_j<j^3$ for all $j=1,\ldots,n$ and all the differences $a_i-a_j$ are pairwise distinct. Let $m$ be the smallest positive integer number which is not of the form $a_i-a_j$. Since there are at most $\binom{n}{2}<n^2$ such a difference, so $m<n^2$. Let $x$ be a good number if both $x$ and $x+m$ are not of the form $a_i-a_j+a_k$. Since there are at most $2\binom{n}3=\frac{n(n-1)(n-2)}{3}< n^3$ such "bad number". So if $a_{n+1}$ be the smallest good number then $a_{n+1}\leq n^3$. Now if there is some $1\leq j\leq n$ such that $a_{n+1}-a_j=m$ then $m$ has been chosen in the next step. If not, we just put $a_{n+2}=a_{n+1}+m$ then $a_{n+2}<n^3+n^2<(n+1)^3$ and in the next step $m$ has been chosen. So we are done. Thanks for the solution. i shall go through it.