Prove that there exists a subset $S$ of positive integers such that we can represent each positive integer as difference of two elements of $S$ in exactly one way.
Problem
Source: Iran Third Round Problems 1993 – Poblem 4
Tags: number theory, number theory proposed
29.07.2011 17:21
I have rediscovered this result, then found it in [R.K.Guy - Unsolved Problems in Number Theory] E25. I quote from there Quote: Marshall Hall (1947) proved the existence of an increasing sequence such that every positive integer occurs uniquely as the difference of two members of the sequence. For example $1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980,2001,\ldots$ defined by $a_1 = 1$, $a_2=2$, $a_{2n+1} = 2a_{2n}$, $a_{2n+2} = a_{2n+1} + r_n$, where $r_n$ is the least positive integer which cannot be represented in the form $a_j - a_i$ with $1\leq i < j \leq 2n+1$.
28.04.2016 20:07
Filling in the details of the solution mentioned in post #2: Define the sequence $a_1 = 1$, $a_{2n} = a_{2n-1} + r_{2n-1}$, $a_{2n+1} = 2a_{2n}$, where $r_k$ is the least positive integer that cannot be written as the difference of two elements of $a_1, a_2, ... a_k$. Every positive integer appears as the difference of two elements of the sequence $a_i$ because of how $r_k$ is defined. Now we show each positive integer appears at most once as the difference of two elements of sequence $a_i$. By definition $a_{2n+1}$ can not cause a difference to repeat when added. If $a_{2n}$ caused a difference to repeat, that difference would have to be at least the distance between $a_{2n}$ and $a_{2n-2}$, which is $\frac{1}{2}a_{2n-1} + r_{2n-1}$. This difference must be replicated by $a_{2n-1}$ and some other element, because the range of the earlier elements of the sequence is too small. But $a_{2n} - a_{2n-1} = a_s - a_t \rightarrow a_{2n}-a_s = a_{2n-1}-a_t$, impossible by definition of $a_{2n}$.
01.09.2016 19:37
can you show more ?? I