Competition problem — Combinatorics

Library / /42 of 57

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it 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$ , клетки которой покрашены в чёрный и белый цвета. При этом во всех столбцах поровну чёрных клеток, в то время как во всех строках разные количества чёрных клеток. Каково максимальное возможное количество пар соседних по стороне разноцветных клеток?

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.