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

Давайте рассмотрим крест, полученный из доски 4x4 после удаления угловых клеток. У нас остаётся 12 клеток. Чтобы обойти все клетки конём ровно один раз и вернуться в исходную клетку, должен существовать замкнутый гамильтонов цикл. Рассмотрим раскраску креста в шахматном порядке. Легко видеть, что клеток одного цвета на 2 больше, чем другого. Например, если раскрасить центральную клетку в черный цвет, то черных клеток будет 7, а белых - 5. При каждом ходе конь меняет цвет клетки. Если бы существовал замкнутый гамильтонов цикл, то после каждого хода конь оказывался бы на клетке противоположного цвета, и в итоге количество клеток каждого цвета должно было бы быть одинаковым. Так как количество клеток каждого цвета не одинаково, то невозможно обойти крест ходом коня, побывав на каждой клетке ровно один раз и вернувшись в исходную клетку. Таким образом, ответ: **0**.