4. From the set $\{1,2,3, \ldots, 99\}$, select the largest number of elements such that the sum of no two selected numbers is a multiple of eleven. (Explain why the chosen selection has the required property and why no selection with a larger number of elements satisfies the condition.)
SOLUTION. We will divide the numbers from 1 to 99 into eleven groups $T_{0}, T_{1}, \ldots, T_{10}$ based on their remainder when divided by 11:

$$
\begin{aligned}
T_{0}= & \{11,22,33, \ldots, 99\}, \\
T_{1}= & \{1,12,23, \ldots, 89\}, \\
T_{2}= & \{2,13,24, \ldots, 90\}, \\
& \vdots \\
T_{10}= & \{10,21,32, \ldots, 98\} .
\end{aligned}
$$

If we select one number from $T_{0}$ (we cannot select more) and all numbers from $T_{1}, T_{2}, T_{3}, T_{4}$, and $T_{5}$, we get a valid selection of $1+5 \cdot 9=46$ numbers, because the sum of two numbers from 0, 1, 2, 3, 4, 5 is divisible by 11 only in the case of $0+0$, and we have selected only one number from the set $T_{0}$.

On the other hand, in any valid selection, there can be at most one number from the group $T_{0}$ and at most 9 numbers from each of the groups

$$
T_{1} \cup T_{10}, T_{2} \cup T_{9}, T_{3} \cup T_{8}, T_{4} \cup T_{7}, T_{5} \cup T_{6}
$$

because if we select 10 numbers from any group $T_{i} \cup T_{11-i}$, there would be some number from the group $T_{i}$ and some number from the group $T_{11-i}$ among the selected numbers; their sum would then be divisible by 11. Therefore, the total number of numbers in the selection is at most $1+5 \cdot 9=46$.

Note. Perhaps the neat solution looks too tricky. However, initial considerations of any solver quickly lead to it: it is clear that it only depends on the remainders of the selected numbers, so dividing into classes $T_{i}$ and selecting from them is natural. It is clear that only one number can be selected from $T_{0}$, and everything else we need to take care of is the requirement that we do not select a number from the group $T_{i}$ and a number from the group $T_{11-i}$ at the same time. If a number from the class $T_{i}$, where $i \neq 0$, is already selected, we can safely select all numbers from $T_{i}$, which will not violate the studied property. Therefore, it is even clear how all selections of the largest number of numbers look like.