1. $2001 \times 2001$ trees are arranged in a square grid in a park. What is the largest number of trees that can be cut down so that no stump is visible from another tree?

(The trees should have a diameter of 0)

## Solution
Obviously, the trees can be grouped together in groups of 1, 2 or 4 neighboring trees as follows:

- $1000^{2}$ groups of the form $2 \times 2$,
- 1000 groups each of the form $1 \times 2$ and $2 \times 1$,
- 1 single tree.

In each of the $1002001=1001^{2}$ groups, at most one tree may be cut down, because two tree trunks in the same group are mutually visible. We now show that you can cut down all trees whose row and column numbers are odd (that is $1001^{2}$). The solution to the problem is therefore 10012 . Consider any two tree trunks with coordinates $(a, b)$ and $(c, d)$, where $a, b, c, d$ are odd. Let $g>0$ be the greatest common divisor of $a-c$ and $b-d$ (these numbers can also be negative!) and write $a-c=x g$ and $b-d=y g$. Now $x$ and $y$ are not both even after construction. The tree with coordinates $(a+x, b+y)$ lies inside the connecting line of the trunks $(a, b)$ and $(c, d)$ and has not been felled, because at least one of its coordinates is even. Therefore, neither of the two strands is visible from the other.