Track / Stage 7 / 97 of 300 #1497 of 1964

Problem 1497

National Olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.1 Prove it Russian Mathematical Olympiad · Russia

Each cell of a $100 \times 100$ table is colored either in black or in white, so that all columns contain equal numbers of black cells, but no two rows contain equal numbers of black cells. Determine the greatest possible number of pairs of neighboring cells whose colors are distinct. (Two cells are neighboring if they share a side.)

Дана клетчатая таблица $100 \times 100$ , клетки которой покрашены в чёрный и белый цвета. При этом во всех столбцах поровну чёрных клеток, в то время как во всех строках разные количества чёрных клеток. Каково максимальное возможное количество пар соседних по стороне разноцветных клеток?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Set $2n = 100$ . By a counting argument, each column contains $n$ black cells, while the rows contain $0, 1, 2, \dots, n-1, n+1, n+2, \dots, 2n$ black cells in some order.
A row with $i$ black cells contains at most $\min\{2i, 2(2n-i)\}$ dichromatic pairs, so there are at most $2 \cdot (2 \cdot 0 + 2 \cdot 1 + \dots + 2 \cdot (n-1)) = 2n(n-1)$ horizontal dichromatic pairs. Next, consider $n-1$ non-bordering rows with no neighboring rows among them. In each such row at least one cell participates in some vertical monochromatic pair, so there are at least $n-1$ monochromatic vertical pairs. Thus the number of dichromatic pairs is at most $2n(n-1) + 2n(2n-1) - (n-1) = (2n-1)(3n-1)$ .
An example (for $n=4$ ) showing that the estimate is sharp is presented on Fig. 6.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.