18. Тип 11 № 11359 Доска имеет форму креста, который получается, если из квадратной доски 4х4 выкинуть угловые клетки (см. рис.). Можно ли обойти её ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу? В ответе укажите 1, если это возможно, или 0, если невозможно.

Для решения этой задачи нужно понять, как устроен крест из доски 4х4 и как ходит шахматный конь.

Крест из доски 4х4 состоит из 12 клеток (4+4+4=12, но центральная клетка считается один раз, и угловые не вырезаются, поэтому 4+4+4 = 12. Если вырезать угловые клетки из 4х4 (16 клеток), то останется 16 - 4 = 12 клеток).

Теперь давайте разберемся с ходом коня. Конь ходит буквой "Г": две клетки в одну сторону (по горизонтали или вертикали) и одну клетку вбок.

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

У нас 12 клеток. Чтобы обойти все клетки ровно по одному разу и вернуться на исходное поле (это называется Гамильтонов цикл), коню нужно сделать 12 ходов.

Если конь начинает на белой клетке, после 12 ходов он окажется на черной клетке (12 - четное число ходов, поэтому цвет поля меняется 12 раз, возвращаясь к исходному цвету). Чтобы вернуться на исходное поле, нужно сделать четное число ходов. Если мы начинаем на белой клетке, то после 12 ходов мы окажемся на черной, а чтобы вернуться на белую, нам нужен еще один ход (13-й), что противоречит условию, что мы прошли по всем клеткам ровно один раз.

Давайте представим клетки креста и их раскраску:

Крест выглядит так:

_

_| |_

|_|_|_|

|_|

|_|

Раскрасим его:

Б

Ч|Б|Ч

Б|Ч|Б|

Ч

Б

Если мы начинаем на белой клетке, конь должен пройти 12 ходов и вернуться на эту же белую клетку. Но за 12 ходов он окажется на черной клетке. Значит, Гамильтонов цикл невозможен.

Ответ: 0