4*. Find all such positive integers $k$ for which the number

$$
\underbrace{1 \ldots 1 \overbrace{2 \ldots 2}^{k}}_{2000}-\underbrace{2 \ldots 2}_{1001}
$$

is a perfect square.
4. Let $n=1000$. Consider two cases.

$1^{\circ} . k>n$. Then

$$
\underbrace{1 \ldots 12 \ldots 2}_{2 n}-\underbrace{2 \ldots 2}_{n+1}=\underbrace{1 \ldots 1}_{2 n-k} \overbrace{2 \ldots 2}^{k-(n+1)} \underbrace{0 \ldots 0}_{n+1} .
$$

This number ends with $n+1=1001$ zeros. But if a number is a square of a natural number, it must end with an even number of zeros! Therefore, this number cannot be a square of a natural number.

$2^{\circ} . k \leqslant n$. Then

$$
\begin{aligned}
\underbrace{1 \ldots 1 \overbrace{2 \ldots 2}^{k}}_{2 n}-\underbrace{2 \ldots 2}_{n+1}=\underbrace{1 \ldots 10 \ldots 0}_{2 n-k}-\underbrace{2 \ldots 20 \ldots 0}_{k} & = \\
& =10^{k}(\underbrace{1 \ldots 1}_{2 n-k}-\underbrace{2 \ldots 2}_{n+1-k})
\end{aligned}
$$

This number ends with $k$ zeros. As explained above, for it to be a square of a natural number (henceforth, we will call squares of natural numbers perfect squares), $k$ must be even. Let $l=\frac{k}{2}$.

It is clear that the number (1) is a perfect square if and only if the number

$$
A=\underbrace{1 \ldots 1}_{2 n-2 l}-\underbrace{2 \ldots 2}_{n+1-2 l}
$$

is a perfect square.

Notice that

$$
A=\frac{1}{9} \cdot \underbrace{9 \ldots 9}_{2 n-2 l}-\frac{2}{9} \cdot \underbrace{9 \ldots 9}_{n+1-2 l}=\frac{1}{9}\left(10^{2 n-2 l}-1-2\left(10^{n+1-2 l}-1\right)\right)
$$

(see fact 11). Let $B=9 A$. The number $A$ is a perfect square if and only if $B=9 A$ is a perfect square. Write the expression for $B$ in the following form:

$$
B=10^{2 n-2 l}-2 \cdot 10^{n+1-2 l}+1=\left(10^{n-l}\right)^{2}-2 \cdot 10^{n-l} \cdot 10^{1-l}+1
$$

For $l=1$, the right-hand side of (2) becomes the formula for the square of a difference:

$$
B=\left(10^{n-1}\right)^{2}-2 \cdot 10^{n-1}+1=\left(10^{n-1}-1\right)^{2}
$$

Let $l>1$.

Now notice that if $X=Y^{2}$ is a square of a natural number, then the nearest perfect square (less than $X$) is $(Y-1)^{2}=Y^{2}-2 Y+1$. That is, if a number $Z$ is such that

$$
Y^{2}-2 Y+1\left(10^{n-l}\right)^{2}-2 \cdot 10^{n-l}+1
$$

Then, by the previous observation, this number cannot be a perfect square, so only $l=1$ (and, therefore, only $k=2$) satisfies the condition.