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