10.4. A $100 \times 100$ grid is given, with cells colored black and white. In each column, there are an equal number of black cells, while in each row, the number of black cells is different. What is the maximum possible number of pairs of adjacent cells of different colors? (I. Bogdanov)
Answer. $6 \cdot 50^{2}-5 \cdot 50+1=14751$ pairs.

Solution. Let the side length of the table be $2 n = 100$ (so $n=50$) and number the rows from top to bottom and the columns from left to right with numbers from 1 to $2 n$.

In each row, there can be from 0 to $2 n$ black cells. Since the number of black cells in all rows is different, these numbers are all numbers from 0 to $2 n$, except one (say, except $k$). Then the total number of black cells is $(0+1+\ldots+2 n)-k=2 n^{2}+n-k$. On the other hand, since the number of cells in all columns is the same, the total number of black cells must be divisible by $2 n$. Therefore, $k=n$, and in all columns there are $2 n^{2} / (2 n) = n$ black cells.

Now let's estimate the number of pairs of adjacent cells of different colors, considering separately pairs of cells adjacent horizontally and vertically.

If there are $i \leqslant n-1$ black cells in a row, then they can participate in no more than $2 i$ horizontal pairs. If there are $i \geqslant n+1$ black cells in a row, the same reasoning can be applied to the white cells, of which there are $2 n-i \leqslant n-1$. Therefore, the number of horizontal pairs of different colors is no more than $2 \cdot(2 \cdot 0+2 \cdot 1+\ldots+2 \cdot(n-1))=2 n(n-1)$.

Now let's estimate the number of vertical pairs. Consider any row with an even number from 2 to $2(n-1)$; let there be $i$ black cells in it. Then either in the row above or in the row below it, the number of black cells is not equal to $100-i$; therefore, one of the vertical pairs in which the cells of our row participate will be of the same color. Therefore, there are at least $n-1$ same-color vertical pairs. Since the total number of vertical pairs is $2 n(2 n-1)$, the number of different-color vertical pairs is no more than $2 n(2 n-1)-(n-1)$. Therefore, the total number of different-color pairs is no more than $2 n(n-1)+\left(4 n^{2}-3 n+1\right)=6 n^{2}-5 n+1=14751$.

It remains to provide an example in which the specified number of pairs is achieved. Draw a diagonal from the upper left corner to the lower right corner in our $2 n \times 2 n$ table. All cells lying on or below the diagonal will be painted black if they are in even rows, and white otherwise (coloring "by rows"). All cells lying above the diagonal will be painted black if the sum of their row and column numbers is even, and white otherwise (checkerboard coloring). An example of such a coloring for $n=4$ is shown in Fig. 3. It is easy to verify that in each column there are exactly $n$ black cells, in the $2 i$-th row there are $n+i$ black cells, and in the $(2 i-1)$-th row there are $-n-i$ black cells. Moreover, all the estimates above are achieved.

Comment. Only the answer - 0 points.

Only the answer and a correct example - 2 points.

Only the proof of the exact estimate - 4 points.

Proof of the exact estimate only for the number of vertical or only for the number of horizontal different-color pairs - 2 points (can be combined with points for a correct example).

Proved that there is no row containing exactly 50 black cells - 1 point, if there are no other significant advances in the work (otherwise this point is not added).