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

Для того, чтобы обход шахматного коня был возможен и заканчивался в начальной клетке (замкнутый маршрут), необходимо, чтобы количество клеток на доске было четным. На данной доске 12 клеток (16 - 4 = 12). Таким образом, задача сводится к поиску гамильтонова цикла на графе, где вершины - клетки доски, а ребра - ходы коня. Так как доска имеет форму креста, то можно показать, что такой обход существует. Один из возможных обходов: 1-6-8-11-9-4-2-7-5-12-10-3-1 Таким образом, обход конём возможен. Ответ: 1