6. Find the largest possible number of integers that can be selected from the set $\{1,2,3, \ldots, 100\}$ such that no two of them differ by 2 or 5.
SOLUTION. First, we will show that from any seven consecutive numbers, denoted as

$$
a, a+1, a+2, a+3, a+4, a+5, a+6,
$$

we can select at most three numbers in the required way. To do this, we divide all seven numbers into three sets

$$
A=\{a, a+2, a+5\}, \quad B=\{a+1, a+3\}, \quad C=\{a+4, a+6\}.
$$

Since we can select at most two numbers from set $A$ and at most one number from each of sets $B$ and $C$, it suffices to exclude the case where two numbers are selected from set $A$ (necessarily $a+2$ and $a+5$) and one number is selected from each of sets $B$ and $C$. In this case, due to the number $a+2$, the number $a+6$ must be selected from $C$, and due to the number $a+5$, the number $a+1$ must be selected from $B$. The simultaneous selection of numbers $a+1$ and $a+6$ is, however, impossible.

Using the proven property, we can now easily explain why from all 100 given numbers from 1 to 100, which we have at our disposal, it is not possible to select more than 44 numbers in the required way. For this, from all 100 numbers, we form 14 disjoint sets of seven consecutive numbers

$$
\{1,2,3,4,5,6,7\}, \quad\{8,9,10,11,12,13,14\}, \ldots, \quad\{92,93,94,95,96,97,98\}
$$

excluding only the two largest numbers 99 and 100. As we have shown, from each of the listed sets of seven, we can select at most three numbers, so the total number of selected numbers indeed never exceeds the number $14 \cdot 3 + 2 = 44$.

In the final part of the solution, we will show that selecting 44 numbers is possible and that it is unique (even though the problem statement does not require this). Suppose we have any valid selection of 44 numbers. According to the previous paragraph, we know that the selected numbers must include the pair 99 and 100. If we modify the composition of 14 disjoint sets of seven to

$$
\{3,4,5,6,7,8,9\}, \{10,11,12,13,14,15,16\}, \ldots, \quad\{94,95,96,97,98,99,100\}
$$

we conclude that the selected numbers must also include the numbers 1 and 2. It is clear that by using other compositions of 14 sets of seven, always consisting of some of the first sets from (1) and some of the last sets from (2), we can deduce that the selected numbers must also include the pairs 8 and 9, 15 and 16, ..., 92 and 93, a total of 15 pairs of consecutive numbers, which give remainders 1 and 2 when divided by seven.

What can we further conclude about the remaining $44 - 30 = 14$ selected numbers? Thanks to the proven property, we know that these must be numbers selected one from each of the 14 sets (1); since in each of these sets, the two smallest numbers are definitely selected, the third selected number in the set must be the one that is the fifth smallest in the set.

We have shown that every valid selection of 44 numbers must look like this:

$$
\{1,2,5\} \cup \{8,9,12\} \cup \{15,16,19\} \cup \ldots \cup \{92,93,96\} \cup \{99,100\}
$$

That this selection, composed of 14 triples and one pair, is indeed valid, we can easily explain: two numbers from the same group differ by 1, 3, or 4; the difference between any two numbers in adjacent groups is one of the numbers 3, 4, 6, 7, 8, 10, or 11; numbers from non-adjacent groups have differences of at least 10.

GUIDING PROBLEMS:

N1. Given the set of numbers $\{1,2,3,4,5,6,7,8,9,10\}$. Find all its subsets with the largest possible number of elements such that no two of them differ by 2 or 5. $[\{1,2,5,8,9\},\{2,3,6,9,10\}]$

N2. Determine for which natural numbers $n, n \geqq 2$, it is possible to select distinct even numbers from the set $\{1,2, \ldots, n-1\}$ such that their sum is divisible by $n$. [54-C-I-2]

N3. For which natural numbers $n$ can four distinct numbers $a, b, c, d$ be selected from the set $\left\{n, n+1, n+2, \ldots, n^{2}\right\}$ such that $a b = c d$? [54-C-S-2]

N4. From the set $\{1,2,3, \ldots, 99\}$, select the largest possible number of numbers such that the sum of no two selected numbers is a multiple of eleven. [58-C-I-5]

N5. From the set $\{1,2,3, \ldots, 99\}$, several different numbers are selected such that the sum of no three of them is a multiple of nine.

a) Prove that among the selected numbers, there are at most four divisible by three.

b) Show that the selected numbers can be 26. [58-C-II-3]