Задача 1: Клетки шахматной доски n × n раскрашены в синий и желтый цвета. Докажите, что либо ладья может пройти по синим клеткам с нижнего края на верхний, либо король может пройти с левого края на правый по желтым клеткам (то есть из двух возможностей всегда есть ровно одна!)

Решение:

1. Пусть ладья не может пройти как требуется. Добавим снизу синюю горизонталь, перекрасим недостижимые с нее синие клетки в белый цвет, и сделаем жирными все стороны отрезков, отделяющие синюю клетку от желтой.

   Из каждого внутреннего узла выходит четное число жирных отрезков.

2. На верхней и нижней границах нет концов жирных отрезков.

3. На правой и левой границе есть концы жирных отрезков.

4. Змейка может по жирным отрезкам проползти с левого края на правый.

5. Король может пройти по желтым клеткам с левого края на правый.

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

7. Клетки, которые не требуются для проходов ладьи, сделаем белыми (не цветными!). Назовем такую раскраску неожиданной. Докажите, что в неожиданной раскраске нет целиком желтой горизонтали.

8. Занумеруем горизонтали снизу вверх, и номер горизонтали назовем высотой клетки. Выберем для доски данного размера минимальную неожиданную раскраску – то есть раскраску с наименьшей возможной суммой высот цветных клеток (почему такая найдется?).

9. Докажите, что на минимальной раскраске у каждой цветной клетки не более двух соседей ее цвета.

10. Ситуацию, когда в квадратике 2 × 2 ровно три клетки – цветные одного цвета, а оставшаяся клетка – нижняя, назовем уголком, при этом оставшуюся клетку квадратика назовем дополнением, а клетку по диагонали от нее – вершиной уголка. Докажите, что в неожиданной раскраске есть уголок.

11. Дополнение уголка либо белая клетка, либо крайняя клетка маршрута противоположного цвета, либо вершина уголка противоположного цвета.

12. Если дополнение уголка – белая клетка, то раскраска не минимальна.

13. Если дополнение уголка – крайняя клетка маршрута противоположного цвета, то раскраска не минимальна.

14. Дополнение уголка с минимальной суммой высот не является вершиной другого уголка.

15. Неожиданных раскрасок не существует.

16. При любой раскраске в два цвета верно ровно одно из двух: либо ладья может пройти по синим клеткам снизу вверх, либо король может пройти по желтым клеткам справа налево.

Задача 2: Если существуют две непересекающиеся ломаные внутри квадрата, одна из которых соединяет верхнюю сторону с нижней, а вторая – правую с левой, то существует неожиданная раскраска некоторой шахматной доски.

Задача 3: Если внутри квадрата проведены две ломаные, одна из которых соединяет верхнюю сторону с нижней, а вторая – правую с левой, то эти ломаные пересекаются.

Задача 4: Докажите, что игра в гекс не может закончится вничью.

Задача 5: Клетки шахматной доски n × n раскрашены в синий и желтый цвета. Докажите, что ферзь может выбрать цвет так, что он мог гулять по всем клеткам этого цвета, не наступая на клетки другого цвета (перепрыгивать можно!).

Задача 6: Шах разбил свой квадратный одноэтажный дворец на 64 одинаковые квадратные комнаты, разделил комнаты на квартиры (проделав двери в некоторых перегородках между комнатами) и в каждой квартире поселил по жене. Жены могут ходить по всем комнатам своей квартиры, не заходя к другим. Известно однако, что в каждой комнате есть стенка, общая с какой-нибудь другой квартирой. Какое наименьшее число жен может быть у шаха?