Bogdanov I.i.

Given a $100 \times 100$ grid, the cells of which are colored black and white. In all columns, there are an equal number of black cells, while in all rows, there are different numbers of black cells. What is the maximum possible number of pairs of adjacent (by side) cells of different colors?
Number the rows from top to bottom and the columns from left to right with numbers from 1 to 100.

In each row, there can be from 0 to 100 black cells. Since the number of black cells in all rows are different, these numbers are all from 0 to 100, except for one (say, except for \( k \)). Therefore, the total number of black cells is \((0+1+\ldots+100)-k=5050-k\). On the other hand, since the number of black cells in all columns is the same, the total number of black cells must be divisible by 100. Thus, \( k=50 \), and in all columns there are \( 5000: 100=50 \) black cells.

Estimation. If a row has \( n \leq 49 \) black cells, then they can participate in no more than 98 horizontal pairs. If a row has \( n \geq 51 \) black cells, the same reasoning can be applied to the white cells, of which there are \( 100-n \leq 49 \). Therefore, the number of horizontal pairs of different colors is no more than \( 2(2 \cdot 0+2 \cdot 1+\ldots+2 \cdot 49)=4900 \).

Now let's estimate the number of vertical pairs. Consider any row with an even number from 2 to 98; let it have \( n \) black cells. Then either the row above or the row below it has a number of black cells not equal to 100 \( n \); thus, one of the vertical pairs involving the cells of our row will be of the same color. Therefore, there are at least 49 vertical pairs of the same color. Since the total number of vertical pairs is 9900, the number of different-colored vertical pairs is no more than \( 9900-49=9851 \). Therefore, the total number of different-colored pairs is no more than \( 9900+9851=14751 \).

Example. Draw a diagonal from the top left corner to the bottom right corner of our table. All cells lying on or below the diagonal will be painted black if they are in even-numbered rows, and white if they are in odd-numbered rows (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 if it is odd ("chessboard" coloring). An example of such a coloring for an \( 8 \times 8 \) table is shown in the figure. It is easy to verify that each column has exactly 50 black cells, the \( 2n \)-th row has \( 50+n \) black cells, and the \( (2n-1) \)-th row has \( 50-i \) black cells. Moreover, all the estimates above are achieved.

![](https://cdn.mathpix.com/cropped/2024_05_06_4c5de22fca2213ac0444g-24.jpg?height=352&width=368&top_left_y=2122&top_left_x=845)

## Answer

14751 pairs.