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