4. Determine the smallest natural number $n$ with the following property: If we choose $n$ different natural numbers less than 2006, there are two among them such that the ratio of the sum and the difference of their squares is greater than three.
SOLUTION. First, we will determine for which natural numbers $a, b$ the mentioned inequality holds

$$
\frac{a^{2}+b^{2}}{a^{2}-b^{2}}>3
$$

For the fraction on the left side to be positive, it must be that $a^{2}>b^{2}$, or $a>b$. If this necessary condition is met, we multiply both sides of the inequality by the positive number $a^{2}-b^{2}$ and through further manipulations we get

$$
\begin{aligned}
a^{2}+b^{2} & >3\left(a^{2}-b^{2}\right), \\
4 b^{2} & >2 a^{2}, \\
b \sqrt{2} & >a .
\end{aligned}
$$

We have found that two natural numbers $a, b$ satisfy condition $(*)$ if and only if the inequalities $11,414 \ldots=\sqrt{2}
$$

The number 103 could still be included in the group $A_{11}$, since

$$
\frac{103}{73}=1,410 \ldots<1,414 \ldots=\sqrt{2}
$$

What is the significance of the constructed partition for solving the given problem? For any two numbers $a, b$ from the same group $A_{i}$, inequality $(*)$ holds. There are 20 groups $A_{i}$ in total; therefore, if we arbitrarily select 21 numbers from the set $A_{1} \cup A_{2} \cup \ldots \cup A_{20}$, at least two of them will belong to the same group $A_{i}^{2}$, thus satisfying $(*)$. Therefore, the number $n=21$ has the property stated in the problem. However, the number $n=20$ does not: if we select the smallest element from each of the groups $A_{i}$, we get twenty numbers

$$
1,2,3,5,8,12,17,25,36,51,73,104,148,210,297,421,596,843,1193,1688,(* *)
$$

among which there are no two numbers $a, b$ satisfying $(*)$, because according to our construction, the ratio of the next number to the previous one is always greater than $\sqrt{2}$.

It should be noted that merely listing the twenty numbers $(* *)$ from the last paragraph cannot be considered a complete solution to the problem, even if we claim that we have selected this set of twenty "as well as possible", i.e., to have as many elements as possible and for no two of them to satisfy $(*)^{3}$. The impossibility of selecting a similar set of 21 numbers must be convincingly justified; for this, we used the pigeonhole principle applied to the constructed groups $A_{i}$.

Answer: The smallest natural number with the required property is $n=21$.

GUIDING AND SUPPLEMENTARY PROBLEMS: