A set $S$ contains integers $1$ and $2$. $S$ also contains all integers of the form $3x+y$ where $x$ and $y$ are distinct elements of $S$, and every element of $S$ other than $1$ and $2$ can be obtained as above. What is $S$?
Let's start by listing out some elements of $S$ that we can obtain using the given conditions:
- $1$ and $2$ are given as elements of $S$.
- If we take $x = 1$ and $y = 3$, we get $3x + y = 6$, which is an element of $S$.
- If we take $x = 2$ and $y = 3$, we get $3x + y = 9$, which is an element of $S$.
- If we take $x = 1$ and $y = 6$, we get $3x + y = 9$, which is also an element of $S$ (but we already have it).
- If we take $x = 2$ and $y = 6$, we get $3x + y = 12$, which is an element of $S$.
- If we take $x = 3$ and $y = 6$, we get $3x + y = 15$, which is an element of $S$.
- If we take $x = 6$ and $y = 12$, we get $3x + y = 30$, which is an element of $S$.
At this point, we have $1$, $2$, $6$, $9$, $12$, $15$, and $30$ as elements of $S$. We can continue this process to obtain more elements of $S$, but notice that any element of $S$ that is greater than $5$ can be written as $3x + y$ for some $x$ and $y$ in {$1$, $2$, $6$}, because any larger element can be written as the sum of two elements less than itself, and we already have $1$, $2$, $6$, $9$, $12$, $15$, and $30$. Moreover, if we choose $x$ and $y$ from {$1$, $2$, $6$}, then $3x + y$ is less than or equal to $3*6 + 6 = 24$, so we have:
$S = {1, 2, 6, 9, 12, 15, 18, 21, 24, 30}$.
As indicated in MathFail's comment, $3$ is not initially in $S$, and it can't be generated from $3x + y$ using positive integers. Also, the rest of your generated values, i.e., the multiples of $3$, are not in $S$.
Instead, note that for any $y_1 \neq 1$ where $y_1 \in S$, by repeatedly using $x = 1$ with $y$ being the latest generated value, we get $3(1) + y_1 = y_1 + 1(3)$, $3(1) + (y_1 + 1(3)) = y_1 + 2(3)$, $3(1) + (y_1 + 2(3)) = y_1 + 3(3)$, etc., also all being in $S$. Thus, as can be proven by induction, $y_1 + 3k \in S$ for all non-negative integers $k$.
Using this with $y_1 = 2$ shows that all positive integers which have a remainder of $2$ when divided by $3$ are in $S$. Next, along with $1$, since $y_1 = 3(2) + 1 = 7$, then all of the positive integers which have a remainder of $1$ when divided by $3$, except for $4$ since it requires $x = y = 1$ which is not allowed because $x$ and $y$ must be distinct, are also in $S$.
Note since $x,y \in \mathbb{N}^{+} \;\to\; z = 3x + y \in \mathbb{N}^{+}$, then since $S$ starts with just $1$ and $2$, then only positive integers can be generated to be in $S$ (i.e., it doesn't include any non-integral or negative values).
Finally, $S$ doesn't contain any integral multiples of $3$. This is because there are none initially so, if there were any, as all values in $S$ are positive integers, there would be a smallest generated one in $S$. However, because it must be of the form $m = 3x + y$ with $x,y \in S$ then, since $x \gt 0$, we have $y \lt m$ is also a multiple of $3$ which is in $S$, contradicting that it's being used to generate the smallest one of $m$.
This shows $S$ is the set of positive integers apart from $4$ and the integral multiples of $3$.