6. Determine the largest natural number $n \geqq 10$ such that for any 10 different numbers $z$ from the set $\{1,2, \ldots, n\}$, the following statement holds: If none of these 10 numbers is a prime number, then the sum of some two of them is a prime number.

(Ján Mazák)
SOLUTION. We will show that the sought maximum $n$ is equal to 21.

First, we verify that no natural number $n \geq 22$ has the required property. For each such $n$, the set $\{1,2, \ldots, n\}$ contains even numbers $4,6,8, \ldots, 22$, which are not prime numbers (we excluded the smallest even number 2) and the required number of which is $(22-4): 2+1=10$. Since the sum of any two of these 10 listed numbers will not be a prime number (it will be an even number greater than 2), the statement of the problem does not hold for these 10 numbers. Therefore, no $n \geq 22$ satisfies the condition.

Now we prove that $n=21$ has the required property. If we select any 10 different numbers from the set $\{1,2, \ldots, 21\}$, none of which are prime numbers (otherwise there is nothing to prove), we actually select 10 different numbers from the set $M = \{1,4,6,8,9,10,12,14,15,16,18,20,21\}$. We divide it for further purposes into a group of odd numbers and a group of even numbers:

$$
L=\{1,9,15,21\} \quad \text{and} \quad S=\{4,6,8,10,12,14,16,18,20\}
$$

We see that $L$ has 4 elements and $S$ has 9 elements. Therefore, among the 10 selected numbers, there is at least one number from $L (10-9=1)$ and at least 6 numbers from $S (10-4=6)$, meaning that at most 3 numbers from $S$ are not selected $(9-6=3)$. In other words, at least one of any four numbers from $S$ is selected.

We now distinguish which of the odd numbers 1, 9, 15, 21 is selected (this will be a discussion of four cases, which do not necessarily exclude each other).

$\triangleright$ The number 1 is selected. Since $1+4, 1+6, 1+10, 1+16$ are prime numbers and at least one of the four even numbers 4, 6, 10, 16 must be selected (according to the conclusion of the previous paragraph), the statement of the problem holds for the selected 10 numbers.

$\triangleright$ The number 9 is selected. Similarly, we use the four sums $9+4, 9+8, 9+10, 9+14$.

$\triangleright$ The number 15 is selected. This time, we use the four sums $15+4, 15+8, 15+14, 15+16$.

$\triangleright$ The number 21 is selected. In this case, the appropriate four sums are $21+8, 21+10, 21+16, 21+20$.

Note. There are many other ways to show that when selecting any 10 different numbers from the set

$$
M=\{1,4,6,8,9,10,12,14,15,16,18,20,21\}
$$

the sum of some two selected numbers will be a prime number. Usually, more cases need to be considered than in our solution, but one sophisticated method requires no substantial case analysis, and we will now describe it.

We divide the entire set $M$ into 9 mutually disjoint subsets

$$
\{1,4\},\{6\},\{8,9\},\{10\},\{12\},\{14,15\},\{16\},\{18\},\{20,21\}
$$

Since there are 9 subsets, when selecting any 10 different numbers from the set $M$, at least one of the two-element subsets must have both of its elements selected. For each of these, the sum of its elements is a prime number.

## GUIDING AND ADDITIONAL PROBLEMS:

N1. Show that from the set $\{1,2,3, \ldots, 10\}$, 4 different numbers can be selected such that none of them is a prime number and no two of them have a sum that is a prime number. Also find all such selections. [The valid selection $4,6,8,10$ is the only one. It must consist of 4 numbers from the set $\{1,4,6,8,9,10\}$, which has 6 elements. The number 1 cannot be in the selection with the three numbers 4, 6, and 10, so it is "unusable." The same applies to the number 9 due to a similar "conflict" with the three numbers 4, 8, and 10. Thus, only the four even numbers $4,6,8,$ and 10 are possible. Their selection works because the sum of any two of them is also an even number different from 2.]

N2. Show that for any natural number $n \geq 2$, from the set $\{1,2,3, \ldots, 2n\}$, $n-1$ numbers can be selected such that none of them is a prime number and no two of them have a sum that is a prime number. [The selection will have the required property if it is composed, for example, of even composite numbers. This is satisfied by the selection of $n-1$ numbers $4,6,8, \ldots, 2n$.]

D1. Show that the number of all six-digit prime numbers does not exceed 300,000. [Six-digit numbers range from 100000 to 999999, totaling 900000. It is sufficient to show that at least 600000 of them are divisible by 2 or 3. There are 450000 divisible by 2 and 300000 divisible by 3. In the sum $450000+300000=750000$, numbers divisible by both 2 and 3, i.e., divisible by 6, are counted twice. There are 150000 such numbers, so the number of six-digit numbers divisible by 2 or 3 is exactly $750000-150000=600000$. Note: Similarly, we find that there are 660000 six-digit composite numbers divisible by 2, 3, or 5, so the number of six-digit prime numbers does not exceed 240000. Even this estimate is very rough—the exact number of six-digit prime numbers is 68906.]

D2. Find the largest three-digit number such that after erasing any digit, the result is a prime number. [The number 731, see $67-\mathrm{C}-\mathrm{S}-1$]

D3. How many numbers can be selected from the set $\{1,2, \ldots, 2018\}$ such that the difference of any two selected numbers is not a prime number? [505 numbers, see 67-B-II-4]

[^0]: * We say that the parity of the total number of tokens is an invariant of the performed operations.