Some squares of a $1999\times 1999$ board are occupied with pawns. Find the smallest number of pawns for which it is possible that for each empty square, the total number of pawns in the row or column of that square is at least $1999$.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
13.03.2013 08:48
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$.
29.09.2023 11:27
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)