ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65710
Темы:    [ Таблицы и турниры (прочее) ]
[ Раскраски ]
[ Арифметическая прогрессия ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Дана клетчатая таблица 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 пара.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2015/2016
этап
Вариант 4
класс
Класс 10
задача
Номер 10.4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .