Разбиение доски на части

Первое решение. Занумеруем вертикали слева направо числами от до Пусть — верхняя строка квадрата, а — строка сразу под ней. Пусть в Петином разбиении эти строки заняты вертикальными домино …, и горизонтальными домино Очевидно, что оставшуюся часть доски можно разбить на домино (например, на горизонтальные), поэтому такое разбиение существует.

Предположим, что существует Васино разбиение на домино, удовлетворяющее требованиям задачи. Если в васином разбиении какая-то из клеток …, занята вертикальным домино, то это — то же домино, что и в Петином разбиении, и из этих двух клеток нельзя добраться до остальных. Поэтому в Васином разбиении обязательно должны присутствовать домино …, Аналогично, клетки и не могут быть накрыты горизонтальными домино, поэтому они накрыты вертикальными домино и Но тогда из четырёх клеток нельзя попасть в остальные — противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим, что Васе удалось требуемое. Тогда из каждой клетки выходит один синий и один красный отрезок, при этом они идут в разные клетки — иначе из этих двух клеток нельзя было бы добраться до остальных.

Раскрасим все клетки в шахматном порядке в чёрный и белый цвета, и поставим на каждом синем отрезке стрелку от белой клетки к чёрной, а на красном — от чёрной к белой. Тогда из каждой клетки ведёт ровно одна стрелка, и в неё входит ровно одна. Тогда все клетки разбились на циклы, и, если Васе удалось, то получился один цикл из всех клеток.

Пусть — верхняя горизонталь, а — нижняя. Пусть в Петином разбиении присутствуют домино и (такое разбиение возможно, если, например, клетки и покрыть вертикальными домино, а все остальные домино сделать горизонтальными). Тогда эти отрезки будут ориентированы как и Если они находятся в одном цикле, то этот цикл должен пройти от к а затем от к Но такие два пути должны иметь общую клетку, что невозможно.