Путешествие коня по 64 клеткам

[usersname]

Может ли конь, побывать на каждой клетке шахматной доски размером 8x8 ровно один раз и последним ходом возвратиться в исходную позицию? Решить такую же задачу для доски 7x7.
_______________________
Есть идея что с каждой парой ходов кол-во черных и белых клеток уменьшается.

[gris]

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

[Droog_Andrey]

usersname в сообщении #261642 писал(а):

Может ли конь, побывать на каждой клетке шахматной доски размером 8x8 ровно один раз и последним ходом возвратиться в исходную позицию? Решить такую же задачу для доски 7x7.
_______________________
Есть идея что с каждой парой ходов кол-во черных и белых клеток уменьшается.

Идея верная.

Пусть изначальная позиция коня - белое поле. Посчитайте, сколько должно остаться незатоптанных конём клеток каждого цвета после 63 ходов в первом случае и после 48 ходов во втором случае.

[Maslov]

Чётное количество ходов в замкнутом пути - это только необходимое условие существования решения. Другими словами, мы точно можем сказать, что задача неразрешима для доски 7х7, а разрешима ли она для доски 8х8 - вопрос отдельный.

[Droog_Andrey]

Maslov в сообщении #261670 писал(а):

а разрешима ли она для доски 8х8 - вопрос отдельный.

http://mathworld.wolfram.com/KnightsTour.html
http://en.wikipedia.org/wiki/Knight's_t ... 7s_Theorem

[Maslov]

Да все прекрасно знают, что доска 8х8 таким образом обходится - хотелось просто обратить внимание на то, что чётного количества клеток для существования решения не достаточно.

[Droog_Andrey]

Просто в случае $8 \times 8$ проще явно найти замкнутый маршрут, чем доказать его существование.

А вообще для существования замкнутого маршрута на доске $m \times n$, где $m \leqslant n$, необходимым и достаточным является выполнение следующих трёх условий:
1) $mn$ не является нечётным числом, большим $1$;
2) при $1<m<5$ обязательно $m=3$, $n>9$
3) при $m=1$ обязательно $n=1$

Разбор некоторых отдельных случаев см. по второй ссылке выше.

[Maslov]

Droog_Andrey в сообщении #261696 писал(а):

Просто в случае $8 \times 8$ проще явно найти замкнутый маршрут, чем доказать его существование.

А как его найти?
Мы же в разделе "Математика", а не "Программирование".

[Yu_K]

Идея простая - шагайте пока шагается и метки ставьте с номерами ходов на те клетки, где были - если не куда шагать и маршрут не завершен - возвращайтесь на шаг назад - там делайте другой ход (всего вариантов ходов 8 для клеток центре доски, занумеруйте ходы, чтоб не повторяться) и тд. Рекурсивная процедура описана в интернете - поищите.

[Maslov]

Yu_K в сообщении #261718 писал(а):

Идея простая - ... Рекурсивная процедура описана в интернете - поищите.

Спасибо, я знаком с этой простой идеей. Но мне кажется, что когда задача предлагается в разделе "Математика", то предполагается не компьютерный перебор, а какой-то другой способ решения. Может быть, я ошибаюсь.

[usersname]

Так или иначе шахматная доска рассматривается как граф. А шагать по доске как в темноте не имеет смысла.