Комбинаторика на БИБНе
Ошибка.
Попробуйте повторить позже
В клетчатом квадрате 
две клетки одной строки или столбца назовем диполем, если между ними ровно две клетки. Петя решил
отметить как можно больше диполей, закрашивая разными цветами разные диполи (а обе клетки одного и того же диполя — одним цветом).
Какое наибольшее количество диполей он сможет закрасить?
Источники:
Подсказка 1
Это клетчатая задачка на оценку + пример, в которой даже персонаж намекает на способ решения, ведь он как-то там хитро закрашивает доску. А не поможет ли нам какая-то раскраска для получения оценки? Они часто помогают в таких задачах)
Подсказка 2
Давайте разобьём квадрат на 9 маленьких квадратиков 2 на 2 так, что между любыми двумя расстояние в 1 клеточку, и покрасим каждый из них в 4 цвета так, чтобы пары одинаковых цветов могли образовывать диполь. Как нам тогда поможет такая раскраска доказать оценку?
Подсказка 3
Так как у нас нечётное кол-во каждого цвета, то как минимум 4 клетки мы потеряем, а значит, уже не более 60/2 = 30 диполей можно получить, остаётся только нарисовать правильный пример под нашу оценку.
Рассмотрим в нашем квадрате 
квадратов 
.png)
Назовём их выделенными.
Заметим, что если одна клетка некоторого диполя принадлежит какому-то выделенному квадрату, то другая клетка этого диполя принадлежит (соседнему) выделенному квадрату.
На рисунке отмечены номерами 
клетки в выделенных квадратах, так что у любого диполя обе клетки должны иметь один и тот
же номер. Но клеток с данным номером (например, с номером 
) девять, и поэтому при “распределении” клеток с номером 
по диполям
по меньшей мере одна клетка окажется нераспределённой (лишней). Таким образом, для каждого из четырех номеров остаётся
нераспределённой минимум одна клетка среди выделенных квадратов, а значит, всего имеется минимум 
нераспределенные
клетки.
Получаем оценку: максимальное число непересекающихся диполей во всём квадрате 
не больше 
Построим теперь пример на 
диполей. Для этого “отрежем” левый нижний выделенный квадрат. Останется клетчатая
фигура из 
клеток, которая разбивается на квадрат 
и два прямоугольника 
и 
Эта фигура полностью
разбивается на диполи, поскольку любые последовательные 
клеток строки или столбца, очевидно, разбиваются на три
диполя.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
