ВсОШ 2022, 9 класс, задача 7
Петя разбил клетчатый квадрат некоторым образом на домино — клетчатые прямоугольники , и в каждом домино соединил центры двух его клеток синим отрезком. Вася хочет разбить этот же квадрат на домино вторым способом, и в каждом своём домино соединить две клетки красным отрезком. Вася хочет добиться того, чтобы из каждой клетки можно было пройти в любую другую, идя по синим и красным отрезкам. Обязательно ли у него будет возможность это сделать?
(Е. Бакаев)
Ответ
Ответ. Не обязательно.
Первое решение. Занумеруем вертикали слева направо числами от до . Пусть — верхняя строка квадрата, а — строка сразу под ней. Пусть в петином разбиении эти строки заняты вертикальными домино и горизонтальными домино , . Очевидно, что оставшуюся часть доски можно разбить на домино (например, на горизонтальные), поэтому такое разбиение существует.
Предположим, что существует васино разбиение на домино, удовлетворяющее требованиям задачи. Если в васином разбиении какая-то из клеток занята вертикальным домино, то это — то же домино, что и в петином разбиении, и из этих двух клеток нельзя добраться до остальных. Поэтому в васином разбиении обязательно должны присутствовать домино . Аналогично, клетки и не могут быть накрыты горизонтальными домино, поэтому они накрыты вертикальными домино и . Но тогда из четырёх клеток нельзя попасть в остальные — противоречие.
Замечание. Существуют и другие варианты петиного разбиения, при которых требуемое невозможно. Например, если обозначить через строку непосредственно под , то годится любое разбиение, содержащее следующие пять домино: , , , , (такие разбиения существуют).
Второе решение. Предположим, что Васе удалось требуемое. Тогда из каждой клетки выходит один синий и один красный отрезок, при этом они идут в разные клетки — иначе из этих двух клеток нельзя было бы добраться до остальных.
Раскрасим все клетки в шахматном порядке в чёрный и белый цвета, и поставим на каждом синем отрезке стрелку от белой клетки к чёрной, а на красном — от чёрной к белой. Тогда из каждой клетки ведёт ровно одна стрелка, и в неё входит ровно одна. Тогда все клетки разбились на циклы, и, если Васе требуемое удалось, то получился один цикл из всех клеток.
Пусть — верхняя горизонталь, а — нижняя. Пусть в петином разбиении присутствуют домино и (такое разбиение возможно, если, например, клетки и покрыть вертикальными домино, а все остальные домино сделать горизонтальными). Тогда эти отрезки будут ориентированы как и . Если они находятся в одном цикле, то этот цикл должен пройти от к , а затем от к . Но такие два пути должны иметь общую клетку, что невозможно.
В решении должно присутствовать явное и достаточно подробное объяснение конструкции петиного разбиения, противоречащего желаниям Васи.
Приведены несколько домино, которые надо включить в петино разбиение, но полного разбиения с ними не существует.
Полная верная конструкция.
Только локальное верное разбиение, которое можно дополнить до разбиения всего квадрата.
Доказательство того, что приведённое разбиение не удовлетворяет желаниям Васи.
При переборном характере доказательства пропущен один частный случай расположения домино в васином разбиении.
Пропущено более одного случая в доказательстве.
Баллы за описание примера и за доказательство того, что он подходит, суммируются друг с другом.