Мы идем с конем по тору вдвоем

[iad58]

Несколько дней назад fiviol предложил погулять с конем по тороидальному полю 5×5 (то есть по такому, где нижняя горизонталь соседствует с верхней, а крайняя левая вертикаль — с крайней правой), а lithovore заметил: «Можно сделать такое преобразование доски: букву с координатами (x,y) переставить в клетку с координатами (−x+3y, x+3y)(mod 5). Тогда ходу коня на старой доске будет соответствовать ход ладьи на новой».

То есть так, например. В каждом поле доски справа сказано, какое поле левой доски перешло в него.

a5 b5 c5 d5 e5     b1 d2 a3 c4 e5
a4 b4 c4 d4 e4     d5 a1 c2 e3 b4
a3 b3 c3 d3 e3  →  a4 c5 e1 b2 d3
a2 b2 c2 d2 e2     c3 e4 b5 d1 a2
a1 b1 c1 d1 e1     e2 b3 d4 a5 c1

Например, на левой доске конь с c3 может пойти на поля b1, a2, a4, b5, d5, e4, e2 и d1, а на правой доске каждое поле с одной из этих меток находится на одной ортогонали (горизонтали или вертикали) с полем, помеченным c3, то есть видно стоящей там ладье. При этом правая доска не обязана быть тороидальной. Даже, как оговаривает xmyruj, желательно, чтобы не была, потому что на торе, если не оговорено обратное, ладья может совершить нулевой ход, обойдя доску по горизонтали или вертикали и вернувшись туда, откуда пошла.

Это довольно существенная оговорка. Задача в первоначальном виде была сложной по двум причинам: (1) гиппогонали (так я называю линии, по которым ходит конь) менее наглядны, чем диагонали и ортогонали; (2) движение по тору труднее представить, чем по нетору.

Преобразование перевело гиппогонали в ортогонали (а также ортогонали в диагонали, а диагонали — в гиппогонали), поэтому на новой доске ходит не конь, а некоторая ортогональная фигура. Но это вообще-то не ладья, а недальнобойная фигура, ходящая по ортогонали либо на соседнее поле (как вазир), либо через одно (как даббаба). Все бы с ней хорошо (не считая отсутствия удобного названия), но доска-то пока еще тороидальная, и ход a1—d1 — это ход на две клетки влево через край (которого у тора на самом деле нет), a1—e1 — на одну клетку влево, а нам сподручнее думать, что все это — движение вправо (на три или четыре клетки). Вот и было сделано второе упрощение: фигура стала дальнобойной, то есть ладьей, разучившись, однако, ходить через край. Вернее, это не фигура разучилась, а доска развернулась и перестала быть тором.

Однако все это возможно только на доске 5×5, потому что только на ней дальнобойной ладье видно ровно столько же полей, сколько недальнобойному коню.

Comments

[fiviol.livejournal.com]

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

[iad.livejournal.com]

Если ограничиться циклическим сдвигом ортогоналей, диагонали и гиппогонали (которые на торе) тоже уцелеют. Можно, например, сделать так, чтобы центральное поле осталось на месте для большей наглядности:

e3 b4 d5 a1 c2
b2 d3 a4 c5 e1
d1 a2 c3 e4 b5
a5 c1 e2 b3 d4
c4 e5 b1 d2 a3

[menelik3.livejournal.com]

С огромным удовольствием прочитал, спасибо!

[fiviol.livejournal.com]

> поэтому место коня может занять фигура, передвигающаяся только по ортогоналям
Вот этого не понял, что ты имеешь в виду? Гиппогональ можно перевести и в диагональ, и в гиппогональ же.

[iad.livejournal.com]

Модальность получилась неоднозначной. Я имел в виду, что для этой доски можно построить такое преобразование, при котором все ходы по гиппогоналям превращаются в ходы по ортогоналям. Можно, конечно, построить и другие, но это наиболее наглядное, поэтому нам важно и интересно, что оно здесь возможно.

[iad.livejournal.com]

Еще характерно, что только здесь два хода конем в одном направлении равняются одному ходу в другом (например, EEN + EEN = NNW), так же, как два хода вазира равняются одному ходу даббабы, поэтому место коня может занять фигура, передвигающаяся только по ортогоналям.

На тороидальной доске 7×7 получается иначе: там последовательность из двух ходов в одном направлении и двух ходов в другом равняется одному ходу в третьем (например, EEN + EEN + NNW + NNW = EES), как два плюс два хода вазира (с поворотом под прямым углом) равны одному ходу альфиля (по диагонали через одну клетку). Место коня после преобразования доски может занять феникс (из японских «средних шахмат»), ходящий как вазир или альфиль.

b7 d1 f2 a3 c4 e5 g6
c5 e6 g7 b1 d2 f3 a4
d3 f4 a5 c6 e7 g1 b2
e1 g2 b3 d4 f5 a6 c7
f6 a7 c1 e2 g3 b4 d5
g4 b5 d6 f7 a1 c2 e3
a2 c3 e4 g5 b6 d7 f1

Но при этом доска должна остаться тором, развернуть ее уже не удастся.

[iad.livejournal.com]

А на торе 9×9 в силе 3EEN + EES = NNW (или 3EEN + ESS = NWW). Это значит, что если четыре из ходов коня преобразовать в ходы вазира, остальные четыре перейдут в четыре из восьми ходов верблюда. Такой сказочной фигуры даже в Японии не придумали. (В остальные ходы верблюда перейдут ходы по диагонали на четвертую от себя клетку.)

[lithovore.livejournal.com]

Если перевести 4 из ходов коня в ходы вазира, то длина ходов, в которые перейдут остальные 4 хода, будет расти с ростом размера тора как O(n). Причём такая возможность существует не при всех размерах:
Ходы коня, лежащие на перпендикулярных гипоналях (как у Вас), нельзя перевести в ходы вазира линейным преобразованием доски, если размер тора делится на 5.
Ходы коня, лежащие на гипоналях, получающихся друг из друга отражением в ортогонали, нельзя перевести в ходы вазира линейным преобразованием доски, если размер тора делится на 2.
Ходы коня, лежащие на гипоналях, получающихся друг из друга отражением в диагонали, нельзя перевести в ходы вазира линейным преобразованием доски, если размер тора делится на 3.

[iad.livejournal.com]

Вот. Таким образом получается, что для тора 5×5, который мы рассматривали первым, возможны два преобразования, переводящие четыре хода коня в ходы вазира: (с точностью до симметрии и отражения):

a5 c1 e2 b3 d4  |  e3 b4 d5 a1 c2
e3 b4 d5 a1 c2  |  b2 d3 a4 c5 e1
d1 a2 c3 e4 b5  |  d1 a2 c3 e4 b5
c4 e5 b1 d2 a3  |  a5 c1 e2 b3 d4
b2 d3 a4 c5 e1  |  c4 e5 b1 d2 a3

В том и в другом случае другие четыре хода коня переходят в ходы даббабы. Четыре гиппогонали переходят в две ортогонали, потому что они попарно совпадали (по составу клеток).

У тора 7×7 размер не делится ни на что, так что возможны три преобразования:

a7 c1 e2 g3 b4 d5 f6  |  b7 d1 f2 a3 c4 e5 g6  |  f4 a5 c6 e7 g1 b2 d3
g5 b6 d7 f1 a2 c3 e4  |  c5 e6 g7 b1 d2 f3 a4  |  a3 c4 e5 g6 b7 d1 f2
f3 a4 c5 e6 g7 b1 d2  |  d3 f4 a5 c6 e7 g1 b2  |  c2 e3 g4 b5 d6 f7 a1
e1 g2 b3 d4 f5 a6 c7  |  e1 g2 b3 d4 f5 a6 c7  |  e1 g2 b3 d4 f5 a6 c7
d6 f7 a1 c2 e3 g4 b5  |  f6 a7 c1 e2 g3 b4 d5  |  g7 b1 d2 f3 a4 c5 e6
c4 e5 g6 b7 d1 f2 a3  |  g4 b5 d6 f7 a1 c2 e3  |  b6 d7 f1 a2 c3 e4 g5
b2 d3 f4 a5 c6 e7 g1  |  a2 c3 e4 g5 b6 d7 f1  |  d5 f6 a7 c1 e2 g3 b4

В одном из них получается феникс (вазир+альфиль), то есть одна пара гиппогоналей переходит в ортогонали, а другая — в диагонали (такие преобразования, пожалуй, самые интересные). В двух других — вазир+полверблюда.

Для тора 9×9 возможны два преобразования:

b9 d1 f2 h3 a4 c5 e6 g7 i8  |  g5 i6 b7 d8 f9 h1 a2 c3 e4
c7 e8 g9 i1 b2 d3 f4 h5 a6  |  i4 b5 d6 f7 h8 a9 c1 e2 g3
d5 f6 h7 a8 c9 e1 g2 i3 b4  |  b3 d4 f5 h6 a7 c8 e9 g1 i2
e3 g4 i5 b6 d7 f8 h9 a1 c2  |  d2 f3 h4 a5 c6 e7 g8 i9 b1
f1 h2 a3 c4 e5 g6 i7 b8 d9  |  f1 h2 a3 c4 e5 g6 i7 b8 d9
g8 i9 b1 d2 f3 h4 a5 c6 e7  |  h9 a1 c2 e3 g4 i5 b6 d7 f8
h6 a7 c8 e9 g1 i2 b3 d4 f5  |  a8 c9 e1 g2 i3 b4 d5 f6 h7
i4 b5 d6 f7 h8 a9 c1 e2 g3  |  c7 e8 g9 i1 b2 d3 f4 h5 a6
a2 c3 e4 g5 i6 b7 d8 f9 h1  |  e6 g7 i8 b9 d1 f2 h3 a4 c5

В обоих случаях по новой доске ходит опять-таки вазир+полуверблюд.

[fiviol.livejournal.com]

Собрать бы вместе определения всех этих вазиров - верблюдов - альфилей, а то сложно. Причем в лучше в числах, а то слова складывать неудобно.:) Тут аналогия с музыкой: квинты-кварты, конечно, вещь привычная музыкантам, но с точки зрения арифметики равенство "кварта + квинта = октава" выглядит ужасно.

Естественнее всего, конечно, задавать фигуры векторами (на сколько шагов фигура ходит в одном ортогональном направлении и в другом):
Конь - (2;1) (а также (1;2), и еще любая координата хода может быть отрицательной. Но для краткости буду обозначать только ходы, где первая коодината не меньше второй, и обе положительные)
Ладья - (х;0)
Слон - (х;х)

Ходы экзотических фигур надо собрать по твоим комментариям, ты в них легче ориентируешься.

Тогда, например, равенство из твоего прошлого комментария: EEN + EEN + NNW + NNW = EES превратится в арифметическое равенство (по модулю 7):
2*(-2;1) + 2*(1;2) = (-2;6) = (-2;-1)
по-моему, понятное даже тем, кто цифры боится больше, чем буквы.

[iad.livejournal.com]

Это ты упомянул фигуры, не имеющие названий! Такие действительно появляются, главным образом за счет всяких полуверблюдов. Номенклатура такая:

Недальнобойные			Дальнобойные
(1;0) вазир (1;1) фирзан	(2;0) даббаба (2;1) конь (2;2) альфиль	(3;1) верблюд (3;2) зебра	(x;0) ладья (x;½x) всадник (x;x) слон

На торе 3×3 конь вырождается в фирзана, потому что (2;1) ≡ (−1;1) (mod 3). На торе 4×4 остается конем, но ходы его попарно эквивалентны, потому что (2;1) ≡ (−2;1) (mod 4), то есть их всего четыре, а не восемь. После преобразования обоих этих торов коня заменяет вазир.