75th 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^{\prime }>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.