NMO Selection Tests

We will prove that $S$ is the set of all positive integers. The argument hinges on the three facts below:

(1) The set $S$ contains an integer $M \ge 40$ divisible by 4.

(2) If $4k$ belongs to $S$ for some integer $k \ge 2$, then so does $4m$ for all positive integers $m < k$.

(3) The set $S$ contains $4k$ for all integers $k \ge 10$.

Assume the three for the moment and argue as follows: By (1) and (2), $S$ contains all positive multiples of 4 at most 40, and by (3) it contains all multiples of 4 at least 40, so $S$ contains all positive multiples of 4.

Let $a = 3$ and let $b = c = 1$. As 7 is in $S$, so is 3, by (a). Repeat the argument for $a = b = c = 1$ to deduce that $S$ contains 1.

Finally, let $a = 2$ and let again $b = c = 1$. As 5 lies in $S$, so does 2. Combining with the previous paragraphs, it follows that $S$ exhausts all positive integers, as stated.

Proof of (1):

If $N$ is divisible by 4, choose $M = N$. If $N = 4k + 1$, set $a = 2k$ and $b = c = 1$ in (a) to deduce that $2k$ and $2k + 2$ are both in $S$. As $N \ge 160$, the numbers $2k$ and $2k + 2$ are both at least $80 > 40$. Note that exactly one of $2k$ and $2k + 2$ is divisible by 4 and let $M$ be that number.

Proof of (2):

Let $b = c = 2$. By (a), if $4a + 4$ is in $S$, then so is $4a$. Beginning with $M$ provided by (1), statement (2) now follows by backward recursion.

Proof of (3):

We first prove that $S$ contains an integer $P \ge 40$ divisible by 4. By (1), $S$ contains an integer $M \ge 40$ divisible by 4. If $M$ is divisible by 8, let $P = M$. Otherwise, $M \ge 44$ and $M - 4$ is divisible by 8. By (2), $M - 4$ is in $S$, so $P = M - 4$ fits the bill.

Let $b = c = 4$. By (a), if $8a + 16$ is in $S$, then so is $16a$. Note that $16a > 8a + 16$ for $a \ge 3$. Thus, if $S$ contains an integer $k \ge 40$ divisible by 8, then it also contains an integer $k' > k$ divisible by 8. Hence, starting with $P$, we can generate arbitrarily large multiples of 8 lying in $S$. Reference to (2) concludes the proof and completes the solution.