ПОСТРОЕНИЕ ИДЕАЛЬНЫХ МАГИЧЕСКИХ КВАДРАТОВ НЕЧЁТНОГО ПОРЯДКА

 

С ПОМОЩЬЮ ЛАТИНСКИХ КВАДРАТОВ

 

Данная страница является продолжением страниц:

 

http://www.klassikpoez.narod.ru/chebpan.htm

http://www.klassikpoez.narod.ru/p9matr.htm

 

Как я уже писала в указанных статьях, в книге Ю. В. Чебракова приведён метод построения пандиагональных квадратов нечётного порядка с помощью двух латинских квадратов.

Чебраков делит все пандиагональные квадраты нечётного порядка на две группы: квадраты порядков не кратных 3 и квадраты порядков кратных 3.

Для квадратов первой группы автором приведён пример построения пандиагонального квадрата 5-ого порядка (стр. 97). Описание метода смотрите на стр. 98-99. Не буду воспроизводить здесь пример Чебракова. Покажу свою интересную схему составления двух латинских квадратов для построения не только пандиагональных, а идеальных квадратов данной серии порядков, которая несколько отличается от схемы Чебракова. Построенный Чебраковым квадрат 5-ого порядка не является идеальным, он только пандиагональный.

 

Начну с построения идеального квадрата 5-ого порядка. На рис. 1 вы видите первый латинский квадрат.

 

 

Рис. 1

 

Этот квадрат строится очень просто. В первой строке, начиная с правой ячейки, записаны числа натурального ряда в порядке возрастания, в левой ячейке записывается 0. Каждая следующая строка квадрата получается из предыдущей циклическим сдвигом с постоянным шагом (в предыдущих статьях такой циклический сдвиг встречался в нескольких примерах). Теперь составляем второй латинский квадрат (рис. 2):

 

 

Рис. 2

 

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

 

Теперь можно строить идеальный квадрат 5-ого порядка по известной уже читателям формуле:

 

c_ij = 5*a_ij + b_ij + 1

 

На рис. 3 вы видите готовый идеальный квадрат.

 

 

Рис. 3

 

Такая простая схема составления латинских квадратов работает для всех нечётных порядков не кратных 3. Это очень просто доказать. Если посмотреть на латинский квадрат, изображённый на рис. 1, как на нетрадиционный магический квадрат, заполненный числами 0,  1,  2,  3,  4, нетрудно увидеть, что этот квадрат идеальный, то есть сумма чисел в любых строке, столбце и  диагонали (как главной, так и разломанной) равна одному и тому же числу, в данном случае – 10. Понятно, что для латинского квадрата порядка n, рассматриваемого как нетрадиционный магический, магическая константа будет равна сумме чисел от 0 до n-1. Эту сумму легко посчитать по формуле для суммы членов арифметической прогрессии:

 

S = n*(n-1)/2

 

Во втором латинском квадрате всё будет точно так же, потому что он получается из первого отражением относительно горизонтальной оси симметрии (это одно из основных преобразований магических квадратов, которое сохраняет идеальность квадрата). Обозначим любые n элементов первого латинского квадрата (в строке, в столбце или в любой диагонали) a₁, a₂, a₃, … a_n, а соответствующие n элементов второго латинского квадрата b₁, b₂, b₃, … b_n. Имеем:

 

a₁ + a₂ + a₃  + … + a_n = n*(n-1)/2

  b₁ + b₂ + b₃ + … + b_n = n*(n-1)/2

 

Тогда сумма n соответствующих элементов строящегося идеального магического квадрата определяется так:

 

S₁ = n*n*(n-1)/2 + n*(n-1)/2 + n = n*(n² +1)/2

 

то есть эта сумма равна магической константе квадрата.

Кроме того, очевидно, что оба латинских квадрата ассоциативны.

Вот оказывается, из каких “идеальных” латинских квадратов строятся идеальные магические квадраты!

 

Покажу ещё несколько примеров.

Составляю латинские квадраты для построения идеального квадрата 7-ого порядка (рис. 4 и рис. 5):

 

 

Рис. 4

 

 

 

Рис. 5

 

На рис. 6 изображён готовый идеальный квадрат 7-ого порядка.

 

 

Рис. 6

 

И ещё один пример – для идеального квадрата 11-ого порядка. На рис. 7 и рис. 8 вы видите латинские квадраты, а на рис. 9 – готовый идеальный квадрат, построенный с помощью этих латинских квадратов.

 

 

Рис. 7

 

 

 

Рис. 8

 

 

 

Рис. 9

 

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

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

 

А теперь для интереса составляю точно по такой же схеме два латинских квадрата для построения квадрата 9-ого порядка [первый квадрат из серии порядков n=3*(2k+1), k=1, 2, 3…]. На рис. 10 и рис. 11 вы видите латинские квадраты.

 

 

 

Рис. 10

 

 

 

Рис. 11

 

Строим квадрат 9-ого порядка из этих латинских квадратов. Как вы думаете, каким получится этот квадрат? Квадрат получается только ассоциативным, но не пандиагональным. Точно такой же результат я получила для квадрата 9-ого порядка, когда построила его методом качелей с тривиальной образующей таблицей: квадрат получился ассоциативный, но не пандиагональный.

 На рис. 12 показываю ассоциативный квадрат, построенный с помощью данной пары латинских квадратов.

 

 

Рис. 12

 

Мне хочется получить первую строку первого латинского квадрата, так чтобы можно было по представленной здесь схеме составить два ортогональных латинских квадрата и построить из них идеальный квадрат 9-ого (а далее и всех следующих порядков кратных 3), подобный квадрату с рис 12. Какой должна быть эта строка? И возможно ли вообще применение представленного алгоритма для построения идеальных квадратов порядков кратных 3? Я имею в виду именно описанную выше схему составления латинских квадратов, а не вообще построение пандиагональных (и идеальных) квадратов с помощью латинских. Как уже было рассказано в предыдущей статье, метод построения пандиагональных (и идеальных) квадратов 9-ого порядка с помощью латинских квадратов уже давно представлен в Интернете вот на этой странице:

 

http://www.grogono.com/magic/9x9.php

 

***

 

Продолжаю исследование. Нашла в своей статье

http://www.klassikpoez.narod.ru/idealob6.htm

идеальный квадрат 9-ого порядка, подобный ассоциативному квадрату с рис. 12 по форме начальной цепочки. Этот квадрат вы видите на рис. 13.

 

 

Рис. 13

 

Очевидно, что этот квадрат отличается от квадрата с рис. 12 только порядком следования чисел в начальной цепочке. Конечно, очень интересно посмотреть, на какие латинские квадраты раскладывается данный идеальный квадрат. Выполняю разложение [в предыдущих статьях показано, как раскладывать пандиагональный (идеальный) квадрат на латинские квадраты]. На рис. 14 и рис. 15 изображены полученные латинские квадраты.

 

 

Рис. 14

 

 

 

Рис. 15

 

Что и требовалось доказать! Схема составления обоих латинских квадратов точно такая же, как во всех предыдущих примерах. Значит, всё дело только в первой строке первого латинского квадрата, а она, как уже отмечалось, определяется начальной цепочкой квадрата.

 

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

 

Теперь покажу составление двух латинских ортогональных квадратов для построения пандиагонального квадрата 15-ого порядка. К сожалению, идеального квадрата с такой формой начальной цепочки у меня не нашлось, а нашёлся в черновых записях только пандиагональный квадрат. Но тем интереснее! Латинские квадраты буду составлять точно по представленной здесь схеме, а начальную цепочку я беру из найденного пандиагонального квадрата.

Составляем первый латинский квадрат (рис. 16). Ещё раз подчеркну, что достаточно заполнить первую строку квадрата, а все следующие строки получаются циклическим сдвигом с постоянным шагом.

 

 

 

Рис. 16

 

Напоминаю, что второй латинский квадрат в рассматриваемом способе получается из первого отражением относительно горизонтальной оси симметрии.  Составляем второй латинский квадрат (рис. 17):

 

 

Рис. 17

 

Два ортогональных латинских квадрата готовы. Складываем матрицы этих квадратов по известной формуле и получаем следующий квадрат (рис. 18):

 

 

Рис. 18

 

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

 

Ещё интересный факт: если первый латинский квадрат взять по-прежнему с рис. 16, а второй латинский квадрат составить по-другому (ниже показано, как именно), то получится снова пандиагональный квадрат 15-ого порядка с “перевёрнутой” начальной цепочкой.

Итак, сначала показываю второй латинский квадрат (рис. 19):

 

 

Рис. 19

 

А теперь строим пандиагональный квадрат из пары ортогональных латинских квадратов с рис. 16 и с рис. 19. Готовый квадрат вы видите на рис. 20.

 

 

Рис. 20

 

Сравните этот квадрат с пандиагональным квадратом на рис. 18. Начальная цепочка “перевернулась”!

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

 

Теперь хочу попробовать составить общую матрицу для построения идеальных квадратов 9-ого порядка, как это сделал автор статьи для построения пандиагональных квадратов данного порядка:

http://www.grogono.com/magic/9x9.php

 

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

 

Кроме того, здесь показана только одна группа частных решений. Те, кто читал мои статьи о методе качелей, знают, как много идеальных квадратов разного вида я построила. Разные квадраты – это значит, что начальная цепочка в них имеет разную форму. В рассмотренной здесь группе частных решений начальная цепочка в квадратах имеет вид “ход конём”. Так вот, интересно посмотреть на идеальные квадраты других частных групп, по какой схеме надо составлять латинские квадраты для построения таких идеальных магических квадратов нечётного порядка.

 

***

 

Составляю желаемую матрицу для построения идеальных квадратов 9-ого порядка.

Напомню, что такая матрица для построения пандиагональных квадратов 9-ого порядка, найденная в статье по указанной чуть выше ссылке, воспроизведена мной на странице:

 

http://www.klassikpoez.narod.ru/p9matr.htm

 

(на рис. 5).

 

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

Общая матрица составляется из двух матриц, первую вы видите на рис. 21, а вторую – на рис. 22. Эти матрицы я составила по частному примеру, приведённому выше.

 

 

Рис. 21

 

 

 

Рис. 22

 

Очевидно, что вторая матрица получена из первой отражением относительно горизонтальной оси симметрии.

На рис. 23 показываю общую матрицу, полученную из приведённых двух матриц.

 

 

Рис. 23

 

К этой матрице, как помнят читатели, должна быть приложена табличка значений символов. Начнём с таких значений символов (рис. 24):

 

 

Рис. 24

 

Напомню, как вычисляются элементы матрицы. Пример:

 

BBCB = 54 + 18 + 3 + 2 = 77

 

то есть значение каждого символа зависит от его позиции.

 

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

 

Итак, общая матрица составлена. Если вы построите по этой матрице квадрат со значениями символов из таблицы на рис. 24, получите идеальный квадрат, изображённый на рис. 13. Проверьте!

 

А я буду экспериментировать. Попробую построить квадрат с другими значениями символов, вот с такими (рис. 25):

 

 

Рис. 25

 

Я просто поменяла значения символов А и В.

Составляю программку для вычисления элементов матрицы, потому что вручную это делать утомительно. К тому же программа мгновенно строит квадрат и исключает ошибки.

Получаю с такими значениями символов следующий идеальный квадрат (рис. 26):

 

 

Рис. 26

 

Очевидно, что этот квадрат получается из квадрата с рис. 13 поворотом на 180 градусов, то есть в этом примере получился эквивалентный квадрат.

Возьму теперь такие значения для символов матрицы (рис. 27):

 

 

Рис. 27

 

С такими значениями получаем следующий идеальный квадрат (рис. 28):

 

 

Рис. 28

 

Теперь получился новый квадрат. Посмотрите, в этом квадрате несколько изменилась форма начальной цепочки. Если смотреть с точки зрения качелей, то шаги качания качелей сменились на симметричные.

Следующий пример, значения символов в таблице на рис. 29, а соответствующий идеальный квадрат – на рис. 30. Значения всех символов циклически переставлены.

 

 

Рис. 29

 

 

Рис. 30

 

Опять получаем новый идеальный квадрат. В этом квадрате начальная цепочка совсем “испортилась”. Но этот квадрат связан с квадратом на рис. 28 комбинированным преобразованием “плюс-минус …”.

И последний пример. Ещё раз циклически переставлю значения всех символов (рис. 31):

 

 

Рис. 31

 

Получаю такой идеальный квадрат (рис. 32):

 

 

Рис. 32

 

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

 

Таким образом, представленная матрица даёт возможность построить несколько существенно различных (то есть не эквивалентных) идеальных квадратов 9-ого порядка. В этом её ценность. Составив одну пару латинских квадратов, мы можем построить только один идеальный квадрат. Матрица даёт обобщение данного метода построения идеальных квадратов.

 

***

 

Решив немного отдохнуть от идеальных квадратов порядков кратных 3, возвращаюсь к идеальным квадратам порядков не кратных 3, с которых начинается эта страница.

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

 

 

Рис. 33

 

Второй латинский квадрат получается из первого отражением относительно горизонтальной оси симметрии. Программа для составления обоих квадратов очень простая, построение идеального квадрата из двух построенных квадратов по известной формуле тоже очень легко запрограммировать. Вот текст программы, которая построит идеальный квадрат любого нечётного порядка не кратного 3. Конечно, максимальный размер такого квадрата зависит от ресурсов памяти, обеспечиваемой языком программирования. Язык QBASIC, на котором написана представленная здесь программа, не позволяет строить очень большие квадраты. Максимально большой квадрат, который мне удалось построить, имеет порядок n=97.

 

ТЕКСТ ПРОГРАММЫ

 

10 OPEN "MK.txt" FOR OUTPUT AS #1

15 PRINT "VVEDITE PORYADOK KVADRATA"

20 INPUT N

25 IF N / 2 - INT(N / 2) = 0 THEN 15

30 IF N / 3 - INT(N / 3) = O THEN 15

40 DIM A(N, N), B(N, N), C(N, N)

45 A(1, 1) = 0

50 FOR I = 2 TO N: A(1, I) = N + 1 - I: NEXT I

55 J = 2

60 A(J, 1) = A(J - 1, N - 1): A(J, 2) = A(J - 1, N)

65 FOR X = 3 TO N: A(J, X) = A(J - 1, X - 2): NEXT X

70 J = J + 1

75 IF J > N THEN 100

80 GOTO 60

100 FOR X = 1 TO N

105 FOR Y = 1 TO N

110 B(X, Y) = A(N - X + 1, Y)

115 NEXT Y

120 NEXT X

125 FOR X = 1 TO N

130 FOR Y = 1 TO N

135 C(X, Y) = N * A(X, Y) + B(X, Y) + 1

140 NEXT Y

145 NEXT X

150 FOR X = 1 TO N

155 FOR Y = 1 TO N

160 PRINT C(X, Y);

165 PRINT #1, C(X, Y);

170 NEXT Y

175 PRINT : PRINT #1,

180 NEXT X

185 CLOSE #1

200 END

 

Введите в программу порядок квадрата (не забывайте, что порядок должен быть нечётным и не кратным 3) и программа мгновенно выдаст вам идеальный квадрат. Приведу пример идеального квадрата 25-ого порядка в том виде, как он записан программой в файл:

 

24  623  597  571  545  519  493  467  441  415  389  363  337  311  285  259  233  207  181  155  129  103  77  51  50

 72  46  20  619  593  567  541  515  489  463  437  411  385  359  333  307  281  255  229  203  177  151  150  124  98

 120  94  68  42  16  615  589  563  537  511  485  459  433  407  381  355  329  303  277  251  250  224  198  172  146

 168  142  116  90  64  38  12  611  585  559  533  507  481  455  429  403  377  351  350  324  298  272  246  220  194

 216  190  164  138  112  86  60  34  8  607  581  555  529  503  477  451  450  424  398  372  346  320  294  268  242

 264  238  212  186  160  134  108  82  56  30  4  603  577  551  550  524  498  472  446  420  394  368  342  316  290

 312  286  260  234  208  182  156  130  104  78  52  26  25  624  598  572  546  520  494  468  442  416  390  364  338

 360  334  308  282  256  230  204  178  152  126  125  99  73  47  21  620  594  568  542  516  490  464  438  412  386

 408  382  356  330  304  278  252  226  225  199  173  147  121  95  69  43  17  616  590  564  538  512  486  460  434

 456  430  404  378  352  326  325  299  273  247  221  195  169  143  117  91  65  39  13  612  586  560  534  508  482

 504  478  452  426  425  399  373  347  321  295  269  243  217  191  165  139  113  87  61  35  9  608  582  556  530

 552  526  525  499  473  447  421  395  369  343  317  291  265  239  213  187  161  135  109  83  57  31  5  604  578

 625  599  573  547  521  495  469  443  417  391  365  339  313  287  261  235  209  183  157  131  105  79  53  27  1

48  22  621  595  569  543  517  491  465  439  413  387  361  335  309  283  257  231  205  179  153  127  101  100  74

 96  70  44  18  617  591  565  539  513  487  461  435  409  383  357  331  305  279  253  227  201  200  174  148  122

 144  118  92  66  40  14  613  587  561  535  509  483  457  431  405  379  353  327  301  300  274  248  222  196  170

 192  166  140  114  88  62  36  10  609  583  557  531  505  479  453  427  401  400  374  348  322  296  270  244  218

 240  214  188  162  136  110  84  58  32  6  605  579  553  527  501  500  474  448  422  396  370  344  318  292  266

 288  262  236  210  184  158  132  106  80  54  28  2  601  600  574  548  522  496  470  444  418  392  366  340  314

 336  310  284  258  232  206  180  154  128  102  76  75  49  23  622  596  570  544  518  492  466  440  414  388  362

 384  358  332  306  280  254  228  202  176  175  149  123  97  71  45  19  618  592  566  540  514  488  462  436  410

 432  406  380  354  328  302  276  275  249  223  197  171  145  119  93  67  41  15  614  588  562  536  510  484  458

 480  454  428  402  376  375  349  323  297  271  245  219  193  167  141  115  89  63  37  11  610  584  558  532  506

 528  502  476  475  449  423  397  371  345  319  293  267  241  215  189  163  137  111  85  59  33  7  606  580  554

 576  575  549  523  497  471  445  419  393  367  341  315  289  263  237  211  185  159  133  107  81  55  29  3  602

 

Как видите, программа действительно очень простая.

Идеальный квадрат 97-ого порядка помещаю на сайт. Кто хочет посмотреть на этот квадрат, он здесь:

 

http://www.klassikpoez.narod.ru/mk/id97.TXT

 

Если вы хотите построить идеальный квадрат порядка больше 97, перепишите программу на другом языке. Из-за простоты и маленького размера программы это можно сделать за 10 минут.

 

ЛАТИНСКИЕ КВАДРАТЫ И МЕТОД КАЧЕЛЕЙ

 

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

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

 

На рис. 34 представляю образующую таблицу, порождающую идеальный квадрат, изображённый на рис. 6.

 

 

Рис. 33

 

Напомню читателям, что в нижней строке образующей таблицы находятся номера циклов качания качелей. Эти номера принимают значения от 1 до n-1, начальной цепочке соответствует нулевой цикл качания качелей. Теперь воспроизведу идеальный квадрат с рис. 6 и раскрашу в нём кроме начальной цепочки ещё два цикла качания качелей (рис. 34).

 

 

Рис. 34

 

Далее воспроизведу первый латинский квадрат с рис. 4, который был составлен для построения этого идеального квадрата (рис. 35):

 

 

Рис. 35

 

Посмотрите, что записано в первой строке этого латинского квадрата. Записаны номера циклов качания качелей из образующей таблицы! А дальше латинский квадрат заполняется так: всем числам набора, соответствующего нулевому циклу качания качелей, в латинском квадрате соответствует число 0, всем числам набора, соответствующего циклу качания качелей с номером 1, в латинском квадрате соответствует число 1 и так далее (смотрите на раскраску в идеальном квадрате и в латинском квадрате).

 

Вот такая чудесная связь латинского квадрата, составленного для построения идеального квадрата, с методом качелей!

 

Такая же связь существует и для порядков кратных 3. Приведу пример с идеальным квадратом 9-ого порядка, который здесь был построен. Воспроизведу идеальный квадрата с рис. 13 (рис. 36) и раскрашу в нём кроме начальной цепочки ещё три цикла качания качелей:

 

 

Рис. 36

 

На рис. 37 представляю образующую таблицу этого идеального квадрата: