Exercise 8. Let $S$ be a set included in $\{1,2,3, \ldots, 199,200\}$. We say that $S$ is pretty if, for all elements $a$ and $b$ of $S$, the number $a-b$ is not a prime number. What is the maximum number of elements in a pretty set included in $\{1,2,3, \ldots, 199,200\}$?

Note: We say that a set $A$ is included in a set $B$ if every element of $A$ is also an element of $B$.
Solution to Exercise 8: Let $S$ be a beautiful set, and consider an element $n$ belonging to $S$: since $n$ is in $S$, $n+2, n+3, n+5, n+7$ are not in $S$.

If $n+1$ is not in $S$, then $n+1, n+2, n+3, n+5, n+7$ are not in $S$. We can have $n+4$ or $n+6$ in $S$, but not both because they differ by 2. In particular, among the 8 integers, at most 2 are in $S$.

If $n+1$ is in $S$, then $n+1+3=n+4, n+1+5=n+6$ are not in $S$. Among the 8 integers between $n$ and $n+7$, there are only two integers in $S: n$ and $n+1$.

It seems natural to divide the integers from 1 to 200 into 25 groups of 8 consecutive integers. Consider a group of 8 consecutive integers $C$, it cannot have more than 2 elements that are in $S$: indeed, either no element of $C$ is in $S$ and the previous statement is true, or there is at least one. In this case, let $n$ be the minimum element in $C$ and $S$: in this case, any element belonging to $C$ and $S$ is between $n$ and $n+7$: there are therefore at most 2 elements that are both in $S$ and $C$.

Thus, in each of the 25 groups, there are at most 2 elements of $S$: a beautiful set therefore has at most $2 \times 25=50$ elements.

Conversely, let's show that there exists a beautiful set of cardinality 50: it is clear that to have such a set, it is better to always have two integers in a block of 8, and if the block starts with $n$, we can take $(n, n+1),(n, n+4),(n, n+6)$. After some tests, the solution that seems to work best is to take pairs of the form $(n, n+4)$ starting from 1: i.e., consider $S$ the set of numbers of the form $4k+1$ with $0 \leq k \leq 49$. This set is well included in $\{1,2, \ldots, 2019,2020\}$ because if $0 \leq k \leq 49, 1 \leq 4k+1 \leq 197$, it has cardinality 50, and since $4k+1-(4l+1)=4(k-l)$, any difference between two elements of $S$ is divisible by 4 and therefore not prime. Thus, $S$ is beautiful.

We therefore obtain that the maximum number of elements of a beautiful set included in $\{1,2,3, \ldots, 199,200\}$ is 50.