Н.Макарова

 

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

 

Доказано, что существование t взаимно ортогональных латинских квадратов порядка n эквивалентно существованию ортогонального массива ОА(t+2,n) (см., например, книгу М. Холла “Комбинаторика”, М.: Мир, 1970). Под ортогональным массивом ОА(t+2,n) понимается матрица размером (t+2)хn², состоящая из элементов 0, 1, 2, … n-1, все строки которой взаимно ортогональны.  Взаимная ортогональность строк матрицы определяется следующим образом:

если a = (a₁, a₂, a₃, … a_n^2), b = (b₁, b₂, b₃, … b_n^2) любые две строки матрицы, то каждая пара (x,y) (x, y есть любые элементы из 0, 1, 2, … n-1) встречается ровно один раз среди пар (a_i,b_i).

 

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

Пример 1. Ортогональный массив ОА(4,3) для двух ортогональных латинских квадратов 3-го порядка (рис. 1).

 

 

Рис. 1

 

Пример 2. Ортогональный массив ОА(5,4) для трёх ортогональных латинских квадратов 4-го порядка (рис. 2).

 

 

Рис. 2

 

Если известен ортогональный массив, группу взаимно ортогональных латинских квадратов построить очень легко. Покажу это на примере ортогонального массива, изображённого на рис. 2. Первые две строки сверху в ортогональном массиве – это координаты. Теперь берём первый столбец ортогонального массива. Первое число в столбце (считая сверху) – координата x, второе число в столбце – координата y; далее идут числа, записанные в ячейке с такими координатами, в первом, втором и третьем латинском квадрате соответственно. Конкретно из первого столбца имеем: в ячейке с координатами (0,0) во всех трёх латинских квадратах запишется число 0. По последнему столбцу ортогонального массива имеем: в ячейку с координатами (3,3) в первом латинском квадрате запишется число 1, во втором латинском квадрате – число 2, в третьем латинском квадрате – число 0 [система координат (x,y) имеет положительную полуось x, направленную вправо, и положительную полуось y, направленную вниз]. На рис. 3 вы видите группу из трёх взаимно ортогональных латинских квадратов 4-го порядка, построенных по данному ортогональному массиву с рис. 2.

 

 

Рис. 3

 

Теперь, когда известно, как из ортогонального массива построить сами ортогональные латинские квадраты, мне удалось построить пары ОЛК 14-го и 26-го порядков, используя описанные в указанной выше книге Холла ортогональные массивы. Покажу эти пары ОЛК, очень интересный результат! Сначала подробно опишу построение ортогонального массива по книге Холла (стр. 279).

Для построения ортогонального массива ОА(4,14) берётся следующая матрица P₀ (рис. 4):

 

 

Рис. 4

 

 Далее строятся матрицы P₁, P₂, P₃ путём циклической перестановки строк в матрице P_0. Матрица A₀ = (P₀,P₁,P₂,P₃). Матрицы A_i (i = 1, 2, …, 10) получаются из матрицы A₀ прибавлением i по модулю 11 к каждому числу в A₀ (за исключением неизвестных x₁, x₂, x₃)_. Матрица A = (A₀, A₁, A₂,…,A₁₀). Матрица B есть ОА(4,3) относительно x₁, x₂, x₃. Наконец, матрица E есть матрица размером 4х11, i-ый столбец которой содержит на каждом месте i.

Искомый ортогональный массив ОА(4,14) = (E,A,B).

На этом Холл заканчивает построение ортогонального массива. Я продолжу подробнее. Сначала покажу матрицу Е. Это очень простая матрица (рис. 5):

 

 

Рис. 5

 

На рис. 6 вы видите ОА(4,3) относительно x₁, x₂, x₃, это матрица В.

 

 

Рис. 6

 

Осталось показать матрицы A_i, из которых образуется матрица А. Не буду показывать все матрицы  A_i, покажу только первые три матрицы (рис. 7–9) и последнюю матрицу (рис. 10). Все остальные матрицы строятся аналогично.

 

Матрица А₀

 

 

Рис. 7

 

Матрица А₁

 

 

Рис. 8

 

Матрица А₂

 

 

Рис. 9

 

Матрица А₁₀

 

 

Рис. 10

 

Всё готово для построения ОА(4,14). На рис. 11 вы видите фрагмент этого массива. Понятно, что эта матрица имеет размер 4х196.

 

 

Рис. 11

 

По готовому ортогональному массиву очень просто построить пару ОЛК 14-го порядка. Как это делается, показано в начале статьи. На рис. 12 показан первый латинский квадрат из этой пары ОЛК, а на рис. 13 – второй латинский квадрат.

 

 

Рис. 12

 

 

Рис. 13

 

Вам ничего не напоминает это построение? Это же очень похоже на алгоритм построения пары ОЛК 10-го порядка! Посмотрите: тоже есть латинский подквадрат 3-го порядка, есть переменные x₁, x₂, x₃.

Закономерности заполнения квадратов очевидны: заполнение в угловом квадрате 11х11 идёт по диагонали, числа записываются в порядке возрастания, после числа 10 пишется число 0. При достижении краёв квадрата диагональ продолжается с другого края квадрата (как если бы квадрат был свёрнут в трубочку по вертикальной или по горизонтальной оси).

Понятно, что переменные x₁, x₂, x₃ могут принимать значения 11, 12, 13 в любой комбинации. Значит, можно построить 6 подобных пар ОЛК. На рис. 14 – 15 показана одна из этих пар с такими значениями переменных: x₁ = 11, x₂ = 12, x₃ = 13.

 

 

Рис. 14

 

 

Рис. 15

 

Кроме того, можно варьировать латинские подквадраты 3-го порядка (на рис. 14-15 подквадраты выделены жёлтым цветом). Понятно, что эти подквадраты тоже должны быть ортогональны. Следует отметить, что варьирование латинских подквадратов 3-го порядка даёт существенно новые, неизоморфные пары ОЛК.

 

Итак, пара ОЛК 14-го порядка получена. Очевидно, что латинские квадраты в этой паре не диагональные (и суммы чисел в диагоналях не равны 91), поэтому пара не пригодна для построения магических квадратов. Надо её преобразовать. Первый латинский квадрат преобразовываю с помощью такой трансформации тождественной перестановки чисел:

 

0  1  2  3  4  5  6  7  8  9  10  11  12  13

0  1 13 3  4  5  6  7  8  9  10  11 12    2

 

Полученный в результате этого преобразования латинский квадрат изображён на рис. 16.

 

 

Рис. 16

 

Преобразовываю второй латинский квадрат с помощью такой трансформации тождественной перестановки чисел:

 

0  1  2  3  4  5  6  7  8  9  10  11  12  13

0  1  3 10  4  5  6  7  8  9  2  12  11  13

 

На рис. 17 вы видите преобразованный второй латинский квадрат.

 

 

Рис. 17

 

Теперь оба латинских квадрата являются нетрадиционными магическими квадратами с магической константой 91. Из этой пары можно построить два магических квадрата, меняя местами латинские квадраты. На рис. 18 показан один из этих магических квадратов. Это первый магический квадрат 14-го порядка, построенный методом латинских квадратов (из пары ортогональных классических латинских квадратов).

 

 

Рис. 18

 

Начальная цепочка в этом магическом квадрате не представляет никакой определённой формы. Но магический квадрат построен! И значит, метод латинских квадратов работает для этого порядка, а также и для всех следующих чётных порядков (для нечётных порядков метод латинских квадратов уже исследован и показан в предыдущих статьях). Всё дело только в умении строить пару ОЛК и если эти латинские квадраты не диагональные, то преобразовывать их так, чтобы получить нужные суммы в диагоналях.

 

Далее в книге Холла приведён пример построения ортогонального массива для пары ОЛК 26-го порядка. Исходная матрица для этого построения показана на рис. 19.

 

 

Рис. 19

 

Дальше всё делается совершенно аналогично построению ортогонального массива для латинских квадратов 14-го порядка. Чтобы построить пару ОЛК 26-го порядка, мне оказалось достаточно одной матрицы A₀. Показываю эту матрицу на рис. 20.

 

 

Рис. 20

 

Ортогональные латинские квадраты сразу даю для конкретных значений переменных: x₁ = 23, x₂ = 24, x₃ = 25. Готовые латинские квадраты из полученной пары ОЛК изображены на рис. 21-22.

 

Первый латинский квадрат 26-го порядка

 

 

Рис. 21

 

Второй латинский квадрат 26-го порядка

 

 

Рис. 22

 

Как видите, аналогия с квадратами 14-го порядка полная. Вот только интересный вопрос: как Холл придумал исходные матрицы P₀ для построения ортогональных массивов?

Точно так же можно варьировать латинские подквадраты 3-го порядка, расположенные в правом нижнем углу обоих латинских квадратов 26-го порядка. Это даст существенно новые (неизоморфные) пары ОЛК.

Преобразовав латинские квадраты в построенной паре ОЛК с помощью трансформации тождественной перестановки чисел, получаю первый магический квадрат 26-го порядка, построенный методом латинских квадратов. Показываю его в виде, записанном программой в файл:

 

599  5  38  597  196  435  336  65  242  498  653  642  95  477  569  364  177  375  120  301  140  266  392  540  449  230

 419  28  6  70  623  223  462  362  92  277  525  654  643  114  507  573  390  204  399  142  328  167  293  567  476  257

 320  446  55  7  97  51  250  489  388  119  296  552  655  644  141  534  600  416  231  429  174  350  191  594  511  261

 221  355  473  82  8  124  77  272  516  414  146  323  579  656  645  165  561  29  442  235  456  201  382  621  530  288

409  248  374  500  109  17  151  103  304  543  440  168  347  606  657  646  195  588  56  468  262  483  228  27  557  315

 255  436  275  401  527  136  10  178  129  331  547  466  200  377  43  658  647  222  610  83  494  289  510  54  581  342

 532  282  463  302  425  554  163  11  205  155  358  574  492  227  404  62  667  625  249  44  110  520  316  81  611  369

343  564  309  490  324  455  589  190  9  209  181  385  601  518  254  431  89  660  626  276  71  137  546  108  40  396

572  370  591  313  517  356  482  608  225  13  236  207  412  30  544  281  458  113  661  627  298  98  164  135  67  423

199  598  397  618  340  521  383  509  37  244  14  263  233  439  57  570  308  480  143  659  628  330  125  162  94  450

152  218  624  424  47  367  548  410  536  61  271  15  290  259  443  84  596  335  512  170  663  629  357  189  116  485

384  179  245  52  459  74  394  575  437  558  91  295  16  317  285  470  111  622  339  539  197  664  630  216  148  504

631  411  183  269  78  478  101  421  602  464  590  118  325  12  344  311  497  138  50  366  566  224  665  251  175  531

666  632  438  210  299  104  505  105  448  31  491  617  145  352  18  371  337  524  173  76  393  593  246  270  202  555

278  662  641  465  237  326  130  529  132  475  58  495  46  172  379  617  398  363  551  192  102  420  620  297  229  585

49  305  668  634  469  264  353  156  559  159  502  85  522  73  194  406  20  433  389  578  219  128  447  321  256  14

474  53  332  669  635  496  291  380  182  586  186  537  112  549  100  226  428  21  452  415  605  243  154  351  283  41

180  501  80  359  670  633  523  318  402  208  613  213  556  147  576  127  253  460  22  479  441  34  273  378  287  68

300  206  528  107  386  671  637  550  345  434  234  42  240  583  166  603  131  280  487  23  503  467  69  405  314  90

88  327  232  563  134  413  672  638  577  372  461  260  64  267  607  193  32  158  307  514  1  533  493  432  341  122

519  115  354  258  582  161  417  673  639  604  407  488  286  96  294  39  217  59  185  334  541  2  560  454  368  149

587  545  139  376  284  609  188  444  651  640  33  426  515  312  123  329  66  247  86  212  361  568  3  486  395  176

4  614  571  169  408  310  35  215  471  652  636  60  453  542  338  150  348  93  274  121  239  365  595  513  422  203

106  133  160  187  214  241  268  303  322  349  373  403  430  457  484  506  538  565  592  619  48  75  79  25  648  676

451  481  508  535  562  584  616  45  72  99  126  153  157  184  211  238  265  292  319  346  381  400  427  650  675  24

63  87  117  144  171  198  220  252  279  306  333  360  387  391  418  445  472  499  526  553  580  615  36  674  26  649

 

Преобразования такие: в первом квадрате выполняется всего одна взаимная замена –  0 à 23, 23 à 0; во втором квадрате  преобразование выполняется в три этапа: 1) 23 à24, 24 à23;  2) 8 à11, 11 à 8;  3) 11 à 16, 16 à 11.

 

***

 

Скачайте электронные книги:

 

“Волшебный мир магических квадратов” – http://narod.ru/disk/5834353000/Magic_squares.pdf.html

 

“Позиционные системы счисления” – http://narod.ru/disk/5936760000/pozic4.pdf.html

 

 

15 - 22 февраля 2009 г.

г. Саратов

 

       Пишите мне!

Приглашаю всех на форум!

На главную страницу