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

Анализ задачи:

Это задача на существование Гамильтонова цикла в графе, где клетки доски — вершины, а возможные ходы коня — рёбра.

Описание доски:

Исходная доска — 4х4, в ней 16 клеток. Угловые клетки (4 штуки) выкинуты. Остаётся 16 - 4 = 12 клеток.

Структура доски (крест):

Форма креста:

  X X
X X X X
X X X X
  X X

Где 'X' — это клетки, по которым можно ходить.

Теория графов (раскраска):

Конь всегда ходит с поля одного цвета на поле другого цвета (при стандартной шахматной раскраске). Гамильтонов цикл возможен только если количество вершин чётное, и если раскрасить вершины в два цвета, то количество вершин каждого цвета должно быть одинаковым.

Раскраска клеток (шахматная):

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

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Уберём углы: 1, 4, 13, 16.

Оставшиеся клетки:

  2 3
5 6 7 8
9 10 11 12

Давайте раскрасим их:

  Ч  Б
Б  Ч  Б  Ч
Ч  Б  Ч  Б

Подсчет клеток по цвету:

• Чёрные (Ч): 2, 6, 8, 9, 11. Итого: 5 чёрных клеток.
• Белые (Б): 3, 5, 7, 10, 12. Итого: 5 белых клеток.

Вывод:

У нас 10 клеток (чётно) и по 5 клеток каждого цвета. Теоретически, Гамильтонов цикл возможен. Но для данной формы креста (неправильный многоугольник) и ходов коня, конкретно для этой конфигурации, такой цикл не существует. Из-за формы креста конь не может попасть на все поля и вернуться на исходное, посетив каждое ровно один раз.

Ответ: 0