Let $n=2a+1$ and consider $n \times n$ board. We need to maximize the number $U$ of unmarked squares. Let $r_i,c_i$ be number of unmarked squares on row $i$ and on column $i$. Then \[\sum_i r_i = \sum_i c_i = U\] Count the number of pairs of (unmarked, marked) squares that are in the same row or column. This number is at least $Un$ by hypothesis. OTOH, this number is exactly \[\sum_i r_i(n-r_i) + \sum_i c_i(n-c_i) = 2Un - \sum_i r_i^2 - \sum_i c_i^2 \leq 2Un - 2\frac{U^2}{n}\] Hence \[Un \leq 2Un - 2\frac{U^2}{n} \ \ \ \longrightarrow \ \ \ U \leq \frac{n^2}{2}\] Since $n = 2a+1$, it follows $U \leq a(a+1)$. To show this is sufficient, we mark the top left $(a+1) \times (a+1)$ and the bottom right $a \times a$ squares. The smallest number of marked squares is $a^2 + (a+1)^2$.

You can easily mark 2 columns of the board and it works. Now suppose this can be done with less than 1999×2 pawns, consider a row that contains at least one pawn. Suppose it contains n pawns, then, in the column of each of these n pawns, there are at least 2001-n pawns. So, in the whole board, there are at least n(2001-n) pawns, which means n(2001-n)<2×1999 so n=1 and it's impossible. (Because there are at least 2000 pawns in that row)