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

Эта задача относится к теории графов и называется задачей о гамильтоновом цикле. Нам нужно определить, существует ли путь, который проходит через каждую клетку ровно один раз и возвращается в начальную точку.

Можно представить доску как шахматную доску. Шахматный конь ходит буквой «Г»: два поля в одном направлении (горизонтально или вертикально) и затем одно поле перпендикулярно.

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

Чтобы обойти все клетки ровно по одному разу и вернуться на исходное поле, конь должен сделать четное число ходов (так как количество клеток четное). В этом случае, если он начал с белой клетки, он должен закончить на белой клетке. Если же он начал с черной, то должен закончить на черной.

Теперь посмотрим на форму креста. Эта фигура, полученная из квадрата 4х4 с выкинутыми углами, имеет 12 клеток. Если мы раскрасим ее как шахматную доску, то увидим, что количество белых и черных клеток будет равным (по 6 клеток каждого цвета).

Однако, при внимательном рассмотрении формы креста, можно заметить, что такая фигура на самом деле не является «сбалансированной» с точки зрения ходов коня. Можно построить конкретный пример, показывающий, что невозможно пройти по всем клеткам ровно один раз и вернуться в исходную точку.

Ответ: 0