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

Ответ: 0

Доска имеет форму креста, полученного из квадратной доски 4x4 путем удаления угловых клеток. Это означает, что у нас есть 12 клеток, по которым нужно пройти конем, чтобы вернуться в исходную точку, посетив каждую клетку ровно один раз.

Рассмотрим доску:

  . . x x
  . x x x
  x x x .
  x x . .

  где x - клетка доски
      . - клетка удалена

Для того чтобы конь мог обойти все клетки и вернуться в исходную, необходимо, чтобы существовал замкнутый маршрут. В данном случае, из-за формы доски и ограничений ходов коня, такой маршрут невозможен. Доказательство основывается на том, что конь всегда переходит с черной клетки на белую и наоборот. Если бы маршрут был возможен, то количество черных и белых клеток должно было быть одинаковым. В нашей доске 12 клеток, 6 черных и 6 белых. Это условие выполняется, но структура доски не позволяет построить такой маршрут.

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

Ответ: 0