обход шахматной доски

[maxal]

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

[ИСН]

Тревожный факт. Почему-то для досок 2X2 и 6X6 такие обходы есть, а для 4X4 - тоже нету...

-- Вт, 2011-08-30, 21:33 --

Ага. Забрезжил какой-то намёк на идею. Берём некий путь - замкнутый, но, может быть, несвязный (состоящий из 2 или более замкнутых петель), и с ним делаем следующую трансформацию: два лежащих рядом параллельных горизонтальных участка (отдельный вопрос, всегда ли такие найдутся) заменяем на два вертикальных. Или наоборот. В химии нечто похожее называется перегруппировкой Стоуна-Уэлса. Замкнутость, очевидно, остаётся как была. Теперь:
- разность между числом вертикальных и горизонтальных ходов изменилась на 4;
- число компонент связности изменилось на 1 (либо одна распалась, либо две склеились);
- хочется, чтобы такими преобразованиями можно было построить любой путь;
- есть очевидный несвязный путь, где число петель чётно, а ходов поровну. Добираясь от него до желаемого нами связного пути, мы неизбежно - - -

[mihailm]

Это с Турнира городов весна 1999 г.

[Macavity]

ИСН в сообщении #479044 писал(а):

Тревожный факт. Почему-то для досок 2X2 и 6X6 такие обходы есть, а для 4X4 - тоже нету...

На самом деле, верно более общее.
Можно найти путь ладьи (Гамильтонов цикл), которая сдвигалась каждый раз на одну клетку, и при этом сделала одинаковое количество ходов по вертикали и горизонтали, если $n=2\mod(4)$. То есть не только для 2, 6 - но и для 10, 14 и т.д.

И это связано с тем, что:
$n^2=4(2(\sum^{\frac n 2-1}_{i=1}{i}+\frac 1 2(\frac n 2 - 1)))+4$

эта формула не просто тавтология - это способ движения ладьи.

[maxal]

доказательство по индукции: http://pech-nik.narod.ru/Math/chess2.html