|
|
 |
Условие
Дана клетчатая таблица 100×100, клетки которой покрашены в чёрный и белый цвета. При этом во всех столбцах поровну чёрных клеток, в то время как во всех строках разные количества чёрных клеток. Каково максимальное возможное количество пар соседних по стороне разноцветных клеток?
Решение
Пронумеруем строки сверху вниз, а столбцы – слева направо числами от 1 до 100.
В каждой строке может быть от 0 до 100 чёрных клеток. Так как количества чёрных клеток во всех строках различны, эти количества – все числа от 0 до 100, кроме одного (скажем, кроме k). Тогда общее число чёрных клеток равно (0 + 1 + ... + 100) – k = 5050 –
k. С другой стороны, так как во всех столбцах клеток поровну, общее число чёрных клеток должно делиться на 100. Значит, k = 50, и во всех столбцах по 5000 : 100 = 50 чёрных клеток.
Оценка. Если в строке n ≤ 49 чёрных клеток, то они могут участвовать не более, чем в 98 горизонтальных парах. Если в строке n ≥ 51 чёрных клеток, аналогичное рассуждение можно применить к белым клеткам, коих 100 – n ≤ 49. Итого, горизонтальных разноцветных пар не больше чем
2(2·0 + 2·1 + ... + 2·49) = 4900.
Оценим теперь количество вертикальных пар. Рассмотрим любую строку с чётным номером от 2 до 98; пусть в ней n чёрных клеток. Тогда либо в строке сверху, либо в строке снизу от неё число чёрных клеток не равно 100 – n; значит, одна из вертикальных пар, в которых
участвуют клетки нашей строки, будет одноцветной. Итого, есть хотя бы 49 одноцветных вертикальных пар. Так как общее число вертикальных пар равно 9900, то разноцветных из них – не больше, чем 9900 – 49 = 9851. Итого, общее число разноцветных пар не больше, чем 9900 + 9851 = 14751.
Пример. Проведём в нашей таблице диагональ из верхнего левого угла в нижний правый. Все клетки, лежащие на или ниже диагонали, покрасим в чёрный цвет, если они лежат в чётных строках, и в белый – если в нечётных (раскраска "по строкам"). Все клетки, лежащие выше диагонали, покрасим в чёрный цвет, если сумма номеров их строки и столбца чётна, и в белый – если нечётна ("шахматная" раскраска). Пример такой раскраски для таблицы 8×8 показан на рисунке. Нетрудно проверить, что в каждом столбце ровно по 50 чёрных клеток, в 2n-й строке есть 50 + n чёрных клеток, а в (2n–1)-й строке – 50 – i чёрных клеток. Кроме того, все оценки выше достигаются.
Ответ
14751 пара.
