Задача 12:

Фигура «верблюд» ходит по доске 10 × 10 ходом типа (1, 3) (то есть, она сдвигается сначала на соседнее поле, а затем сдвигается еще на три поля в перпендикулярном направлении; конь, например, ходит ходом типа (1, 2)). Можно ли пройти ходом «верблюда» с какого-то исходного поля на соседнее с ним?

Решение:

Ответ: нельзя. Рассмотрим шахматную раскраску доски в черный и белый цвета. Тогда, как легко проверить, каждым своим ходом «верблюд» ходит с одного поля на поле того же цвета; иными словами, цвет поля, на котором стоит «верблюд» – инвариант. Но так как два соседних поля имеют разную окраску, то пройти с одного на другое ходом «верблюда» невозможно.

Задача 13:

а) Докажите, что шахматную доску 8 × 8 нельзя замостить 15 фигурками 1 × 4 и одной фигуркой, вида .

б) Докажите, что доску 10 × 10 нельзя замостить фигурками, вида .

в) Докажите, что доску 102 × 102 нельзя замостить фигурками 1 × 4.

Решение:

а) Используйте раскраску доски в два цвета одноцветными и чередующимися по цвету строками.

б) Используйте шахматную раскраску доски.

в) Используйте раскраску в четыре цвета.

Задача 14:

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

Решение:

Рассмотрим раскраску в 4 цвета, такую, что каждая плитка 2 × 2 содержит ровно одну клетку цвета 1, а каждая плитка 1 × 4 – ни одной или две клетки цвета 1. Следовательно, четность числа плиток 2 × 2 должна совпадать с четностью числа клеток цвета 1, что и доказывает утверждение задачи.

Задача 15:

Можно ли доску размерами 4 × N обойти ходом коня, побывав на каждом поле ровно один раз, и вернуться на исходное поле?

Решение:

Раскрасим доску 4 × N в 4 цвета так, чтобы, если конь стоит на поле цвета 1 (соответственно 2), то следующим ходом он встанет на поле цвета 3 (соответственно 4).

Тогда так как полей цветов 1 и 2 столько же, сколько и полей цветов 3 и 4, то в случае наличия обхода конем доски цвета пар (1, 2) и (3, 4) чередуются. Следовательно, всякий раз, как конь встает на поле цвета 3, следующим ходом он должен встать на поле цвета 1 или 2 – а легко видеть, что он может встать только на поле цвета 1. Значит, при обходе доски цвета 1 и 3 чередуются. Но это невозможно, так как тогда конь никогда не встанет на поля цветов 2 и 4. Мы пришли к противоречию.