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

 

КВАДРАТОВ МЕТОДОМ СОСТАВНЫХ КВАДРАТОВ

 

Данная страница является продолжением страницы http://www.natalimak1.narod.ru/aspekty4.htm

 

 

Начну с цитаты из статьи “Completion of the Spectrum of Orthogonal Diagonal Latin Squares” (J. W. Brown и другие):

 

“2. Previous results

 

It is easy to construct orthogonal diagonal latin squares (ODLS) when n is prime to 6, because the n x n square with (i, j) entry i + 2j (modulo n) and its transpose satisfy the definition [4]. The small orders 4, 8 and 9 are easy to construct (see [4]) and side 27 is exhibited in [1]. Gergely [5] showed that if there are ODLS of sides n₁ and n₂ then side n₁n₂ can be realized. So one need only consider those orders divisible by 2 (but not 4) and those divisible by 3 (but not 9)”.

 

В этой цитате содержится очень важный результат: если есть ортогональные диагональные латинские квадраты порядков n₁ и n₂, то можно составить ортогональные диагональные латинские квадраты порядка n₁*n₂.

Это очень напоминает метод составных квадратов для построения магических квадратов. Поэтому и для пар диагональных ОЛК я тоже назвала этот метод методом составных квадратов.

 

В предыдущих частях настоящей статьи были показаны пары ортогональных диагональных латинских квадратов для порядков 4 – 10 и 16, исключая порядки 2, 3 и 6, для которых не существует таких пар ОЛК. Составление пар диагональных ОЛК задача непростая. Метод составных квадратов позволяет легко решить задачу для порядков, представимых в виде произведения двух чисел, для каждого из которых существует пара диагональных ОЛК. Понятно, что минимальный порядок, для которого можно применить метод составных квадратов, равен 16. Я начну демонстрацию метода с составления пары диагональных ОЛК 20-го порядка.

Итак, надо выбрать пары диагональных ОЛК 4-го и 5-го порядков. На рис. 1 показана пара диагональных ОЛК 4-го порядка, а на рис. 2 – пара диагональных ОЛК 5-го порядка.

 

 

Рис. 1

 

 

Рис. 2

 

Замечу, что здесь удобнее записывать латинские квадраты в нетрадиционном виде.

Для построения первого латинского квадрата 20-го порядка надо взять первые квадраты из каждой пары ОЛК. По аналогии с методом составных магических квадратов здесь тоже надо определиться, какой квадрат будет базовым, а какой – основным. От этого зависит разбиение квадрата 20-го порядка. Выберем в качестве базового квадрата квадрат 4-го порядка, а в качестве основного – квадрат 5-го порядка. В таком случает надо разбить матрицу 20х20 на 16 квадратов 5х5 (рис. 3). Число в каждой ячейке базового квадрата показывает, на сколько надо увеличить числа в основном квадрате, помещаемом в соответствующий этой ячейке блок 5х5. Таким образом, аналогия с методом составных магических квадратов полная.

 

 

Рис. 3

 

Первый латинский квадрат готов. Очевидно, что этот латинский квадрат диагональный. Для построения второго латинского квадрата ортогонального построенному квадрату берём вторые латинские квадраты 4-го и 5-го порядков. Всё делаем точно так же, как при построении первого латинского квадрата (см. рис. 4).

 

 

Рис. 4

 

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

 

 1  22  43  64  85  111  132  153  174  195  306  327  348  369  390  216  237  258  279  300

 44  65  81  2  23  154  175  191  112  133  349  370  386  307  328  259  280  296  217  238

 82  3  24  45  61  192  113  134  155  171  387  308  329  350  366  297  218  239  260  276

 25  41  62  83  4  135  151  172  193  114  330  346  367  388  309  240  256  277  298  219

 63  84  5  21  42  173  194  115  131  152  368  389  310  326  347  278  299  220  236  257

 206  227  248  269  290  316  337  358  379  400  101  122  143  164  185  11  32  53  74  95

 249  270  286  207  228  359  380  396  317  338  144  165  181  102  123  54  75  91  12  33

 287  208  229  250  266  397  318  339  360  376  182  103  124  145  161  92  13  34  55  71

 230  246  267  288  209  340  356  377  398  319  125  141  162  183  104  35  51  72  93  14

 268  289  210  226  247  378  399  320  336  357  163  184  105  121  142  73  94  15  31  52

 116  137  158  179  200  6  27  48  69  90  211  232  253  274  295  301  322  343  364  385

 159  180  196  117  138  49  70  86  7  28  254  275  291  212  233  344  365  381  302  323

 197  118  139  160  176  87  8  29  50  66  292  213  234  255  271  382  303  324  345  361

 140  156  177  198  119  30  46  67  88  9  235  251  272  293  214  325  341  362  383  304

 178  199  120  136  157  68  89  10  26  47  273  294  215  231  252  363  384  305  321  342

 311  332  353  374  395  201  222  243  264  285  16  37  58  79  100  106  127  148  169  190

 354  375  391  312  333  244  265  281  202  223  59  80  96  17  38  149  170  186  107  128

 392  313  334  355  371  282  203  224  245  261  97  18  39  60  76  187  108  129  150  166

 335  351  372  393  314  225  241  262  283  204  40  56  77  98  19  130  146  167  188  109

 373  394  315  331  352  263  284  205  221  242  78  99  20  36  57  168  189  110  126  147

 

Следует заметить, что при использовании пары ортогональных латинских квадратов, записанных в нетрадиционном виде, надо несколько изменить формулу для построения магического квадрата. Обозначим матрицу первого латинского квадрата A(a_ij), матрицу второго латинского квадрата –  B(b_ij), матрицу готового магического квадрата - C(c_ij). Тогда формула для построения магического квадрата в случае, когда латинские квадраты записаны в нетрадиционном виде, будет такой:

 

c_ij = n*(a_ij – 1) + b_ij

 

Если поменять латинские квадраты местами, то формула примет вид:

 

c_ij = n*(b_ij – 1) + a_ij

 

А теперь покажу составление пары диагональных ОЛК 25-го порядка методом составных квадратов. Порядок 25 является нечётным порядком не кратным 3, для таких порядков в предыдущих частях статьи показаны две схемы составления пар диагональных ОЛК. Таким образом, это будет уже третья схема.

В качестве исходной пары ОЛК 5-го порядка возьмём следующую пару (рис. 5):

 

 

Рис. 5

 

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

Я буду использовать для построения обоих латинских квадратов 25-го порядка одну и ту же пару ОЛК 5-го порядка, только при построении второго латинского квадрата базовый и основной квадраты меняются ролями. При построении первого латинского квадрата базовым квадратом служит квадрат, изображённый на рис. 5 справа, понятно, что квадрат, изображённый на рис. 5 слева, служит основным. На рис. 6 вы видите готовый латинский квадрат 25-го порядка.

 

 

Рис. 6

 

Этот  диагональный латинский квадрат является нетрадиционным магическим квадратом с магической константой 325, который обладает свойствами ассоциативности и пандиагональности.

Теперь меняю ролями базовый и основной квадраты в той же паре ОЛК 5-го порядка  с рис. 5 и получаю второй латинский квадрат, который, конечно, ортогонален латинскому квадрату с рис. 6 и обладает такими же свойствами. Вы видите этот квадрат на рис. 7.

 

 

Рис. 7

 

Ввожу оба построенных латинских квадрата в программу проверки ортогональности. Программа подтверждает ортогональность квадратов и строит из этой пары ОЛК идеальный магический квадрат, который изображён  на рис. 8.

 

 

Рис. 8

 

Посмотрите, как интересно расположилась в этом идеальном магическом квадрате начальная цепочка (она выделена жёлтым цветом).

 

Поскольку не существует пар ортогональных диагональных латинских квадратов для порядков 2, 3 и 6, под метод составных квадратов для пар диагональных ОЛК попадает очень мало порядков. Например, в первой полусотне это будут такие порядки: 16, 20, 25, 28, 32, 35, 36, 40, 44, 45, 48, 49, 50. Для построения пары диагональных ОЛК 48 порядка нужна пара диагональных ОЛК 12-го порядка, которая теоретически существует, но мне пока неизвестна. Для всех остальных перечисленных порядков я могу построить пару диагональных ОЛК методом составных квадратов. Здесь уже показано составление пар диагональных ОЛК для порядков 20 и 25. Покажу ещё один пример – для порядка 28. Выберу такую пару диагональных ОЛК 4-го порядка, которая даёт пандиагональный магический квадрат, и пару диагональных ОЛК 7-го порядка, дающую идеальный магический квадрат. В результате должна построиться пара диагональных ОЛК 28-го порядка, которая даст пандиагональный магический квадрат. На рис. 9 изображена пара диагональных ОЛК 4-го порядка, на рис. 10 – пара диагональных ОЛК 7-го порядка.

 

 

Рис. 9

 

 

 

Рис. 10

 

Понятно, что удобнее базовым квадратом выбрать квадрат 4-го порядка, а основным – квадрат 7-го порядка. Можно, конечно, сделать и наоборот. Поскольку матрица 28х28 очень большая, буду делать её из двух частей по 14 столбцов в каждой части. На рис. 11 – 12 изображён первый латинский квадрат 28-го порядка.

 

Первый латинский квадрат 28-го порядка – часть 1

 

 

Рис. 11

 

Первый латинский квадрат 28-го порядка – часть 2

 

 

Рис. 12

 

Здесь показываю первый латинский квадрат 28-го порядка полностью:

 

1 3 5 7 2 4 6 8 10 12 14 9 11 13 15 17 19 21 16 18 20 22 24 26 28 23 25 27

7 2 4 6 1 3 5 14 9 11 13 8 10 12 21 16 18 20 15 17 19 28 23 25 27 22 24 26

6 1 3 5 7 2 4 13 8 10 12 14 9 11 20 15 17 19 21 16 18 27 22 24 26 28 23 25

5 7 2 4 6 1 3 12 14 9 11 13 8 10 19 21 16 18 20 15 17 26 28 23 25 27 22 24

4 6 1 3 5 7 2 11 13 8 10 12 14 9 18 20 15 17 19 21 16 25 27 22 24 26 28 23

3 5 7 2 4 6 1 10 12 14 9 11 13 8 17 19 21 16 18 20 15 24 26 28 23 25 27 22

2 4 6 1 3 5 7 9 11 13 8 10 12 14 16 18 20 15 17 19 21 23 25 27 22 24 26 28

22 24 26 28 23 25 27 15 17 19 21 16 18 20 8 10 12 14 9 11 13 1 3 5 7 2 4 6

28 23 25 27 22 24 26 21 16 18 20 15 17 19 14 9 11 13 8 10 12 7 2 4 6 1 3 5

27 22 24 26 28 23 25 20 15 17 19 21 16 18 13 8 10 12 14 9 11 6 1 3 5 7 2 4

26 28 23 25 27 22 24 19 21 16 18 20 15 17 12 14 9 11 13 8 10 5 7 2 4 6 1 3

25 27 22 24 26 28 23 18 20 15 17 19 21 16 11 13 8 10 12 14 9 4 6 1 3 5 7 2

24 26 28 23 25 27 22 17 19 21 16 18 20 15 10 12 14 9 11 13 8 3 5 7 2 4 6 1

23 25 27 22 24 26 28 16 18 20 15 17 19 21 9 11 13 8 10 12 14 2 4 6 1 3 5 7

8 10 12 14 9 11 13 1 3 5 7 2 4 6 22 24 26 28 23 25 27 15 17 19 21 16 18 20

14 9 11 13 8 10 12 7 2 4 6 1 3 5 28 23 25 27 22 24 26 21 16 18 20 15 17 19

13 8 10 12 14 9 11 6 1 3 5 7 2 4 27 22 24 26 28 23 25 20 15 17 19 21 16 18

12 14 9 11 13 8 10 5 7 2 4 6 1 3 26 28 23 25 27 22 24 19 21 16 18 20 15 17

11 13 8 10 12 14 9 4 6 1 3 5 7 2 25 27 22 24 26 28 23 18 20 15 17 19 21 16

10 12 14 9 11 13 8 3 5 7 2 4 6 1 24 26 28 23 25 27 22 17 19 21 16 18 20 15

9 11 13 8 10 12 14 2 4 6 1 3 5 7 23 25 27 22 24 26 28 16 18 20 15 17 19 21

15 17 19 21 16 18 20 22 24 26 28 23 25 27 1 3 5 7 2 4 6 8 10 12 14 9 11 13

21 16 18 20 15 17 19 28 23 25 27 22 24 26 7 2 4 6 1 3 5 14 9 11 13 8 10 12

20 15 17 19 21 16 18 27 22 24 26 28 23 25 6 1 3 5 7 2 4 13 8 10 12 14 9 11

19 21 16 18 20 15 17 26 28 23 25 27 22 24 5 7 2 4 6 1 3 12 14 9 11 13 8 10

18 20 15 17 19 21 16 25 27 22 24 26 28 23 4 6 1 3 5 7 2 11 13 8 10 12 14 9

17 19 21 16 18 20 15 24 26 28 23 25 27 22 3 5 7 2 4 6 1 10 12 14 9 11 13 8

16 18 20 15 17 19 21 23 25 27 22 24 26 28 2 4 6 1 3 5 7 9 11 13 8 10 12 14

 

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

 

Второй латинский квадрат 28-го порядка – часть 1

 

 

Рис. 13

 

Второй латинский квадрат 28-го порядка – часть 2

 

 

Рис. 14

 

Показываю второй латинский квадрат 28-го порядка полностью:

 

15 21 20 19 18 17 16 8 14 13 12 11 10 9 22 28 27 26 25 24 23 1 7 6 5 4 3 2

17 16 15 21 20 19 18 10 9 8 14 13 12 11 24 23 22 28 27 26 25 3 2 1 7 6 5 4

19 18 17 16 15 21 20 12 11 10 9 8 14 13 26 25 24 23 22 28 27 5 4 3 2 1 7 6

21 20 19 18 17 16 15 14 13 12 11 10 9 8 28 27 26 25 24 23 22 7 6 5 4 3 2 1

16 15 21 20 19 18 17 9 8 14 13 12 11 10 23 22 28 27 26 25 24 2 1 7 6 5 4 3

18 17 16 15 21 20 19 11 10 9 8 14 13 12 25 24 23 22 28 27 26 4 3 2 1 7 6 5

20 19 18 17 16 15 21 13 12 11 10 9 8 14 27 26 25 24 23 22 28 6 5 4 3 2 1 7

22 28 27 26 25 24 23 1 7 6 5 4 3 2 15 21 20 19 18 17 16 8 14 13 12 11 10 9

24 23 22 28 27 26 25 3 2 1 7 6 5 4 17 16 15 21 20 19 18 10 9 8 14 13 12 11

26 25 24 23 22 28 27 5 4 3 2 1 7 6 19 18 17 16 15 21 20 12 11 10 9 8 14 13

28 27 26 25 24 23 22 7 6 5 4 3 2 1 21 20 19 18 17 16 15 14 13 12 11 10 9 8

23 22 28 27 26 25 24 2 1 7 6 5 4 3 16 15 21 20 19 18 17 9 8 14 13 12 11 10

25 24 23 22 28 27 26 4 3 2 1 7 6 5 18 17 16 15 21 20 19 11 10 9 8 14 13 12

27 26 25 24 23 22 28 6 5 4 3 2 1 7 20 19 18 17 16 15 21 13 12 11 10 9 8 14

1 7 6 5 4 3 2 22 28 27 26 25 24 23 8 14 13 12 11 10 9 15 21 20 19 18 17 16

3 2 1 7 6 5 4 24 23 22 28 27 26 25 10 9 8 14 13 12 11 17 16 15 21 20 19 18

5 4 3 2 1 7 6 26 25 24 23 22 28 27 12 11 10 9 8 14 13 19 18 17 16 15 21 20

7 6 5 4 3 2 1 28 27 26 25 24 23 22 14 13 12 11 10 9 8 21 20 19 18 17 16 15

2 1 7 6 5 4 3 23 22 28 27 26 25 24 9 8 14 13 12 11 10 16 15 21 20 19 18 17

4 3 2 1 7 6 5 25 24 23 22 28 27 26 11 10 9 8 14 13 12 18 17 16 15 21 20 19

6 5 4 3 2 1 7 27 26 25 24 23 22 28 13 12 11 10 9 8 14 20 19 18 17 16 15 21

8 14 13 12 11 10 9 15 21 20 19 18 17 16 1 7 6 5 4 3 2 22 28 27 26 25 24 23

10 9 8 14 13 12 11 17 16 15 21 20 19 18 3 2 1 7 6 5 4 24 23 22 28 27 26 25

12 11 10 9 8 14 13 19 18 17 16 15 21 20 5 4 3 2 1 7 6 26 25 24 23 22 28 27

14 13 12 11 10 9 8 21 20 19 18 17 16 15 7 6 5 4 3 2 1 28 27 26 25 24 23 22

9 8 14 13 12 11 10 16 15 21 20 19 18 17 2 1 7 6 5 4 3 23 22 28 27 26 25 24

11 10 9 8 14 13 12 18 17 16 15 21 20 19 4 3 2 1 7 6 5 25 24 23 22 28 27 26

13 12 11 10 9 8 14 20 19 18 17 16 15 21 6 5 4 3 2 1 7 27 26 25 24 23 22 28

 

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

 

 15  77  132  187  46  101  156  204  266  321  376  235  290  345  414  476  531  586  445  500  555  589  651  706  761  620  675  730

 185  44  99  161  20  75  130  374  233  288  350  209  264  319  584  443  498  560  419  474  529  759  618  673  735  594  649  704

 159  18  73  128  183  49  104  348  207  262  317  372  238  293  558  417  472  527  582  448  503  733  592  647  702  757  623  678

 133  188  47  102  157  16  71  322  377  236  291  346  205  260  532  587  446  501  556  415  470  707  762  621  676  731  590  645

 100  155  21  76  131  186  45  289  344  210  265  320  375  234  499  554  420  475  530  585  444  674  729  595  650  705  760  619

 74  129  184  43  105  160  19  263  318  373  232  294  349  208  473  528  583  442  504  559  418  648  703  758  617  679  734  593

 48  103  158  17  72  127  189  237  292  347  206  261  316  378  447  502  557  416  471  526  588  622  677  732  591  646  701  763

 610  672  727  782  641  696  751  393  455  510  565  424  479  534  211  273  328  383  242  297  352  8  70  125  180  39  94  149

 780  639  694  756  615  670  725  563  422  477  539  398  453  508  381  240  295  357  216  271  326  178  37  92  154  13  68  123

 754  613  668  723  778  644  699  537  396  451  506  561  427  482  355  214  269  324  379  245  300  152  11  66  121  176  42  97

 728  783  642  697  752  611  666  511  566  425  480  535  394  449  329  384  243  298  353  212  267  126  181  40  95  150  9  64

 695  750  616  671  726  781  640  478  533  399  454  509  564  423  296  351  217  272  327  382  241  93  148  14  69  124  179  38

 669  724  779  638  700  755  614  452  507  562  421  483  538  397  270  325  380  239  301  356  215  67  122  177  36  98  153  12

 643  698  753  612  667  722  784  426  481  536  395  450  505  567  244  299  354  213  268  323  385  41  96  151  10  65  120  182

 197  259  314  369  228  283  338  22  84  139  194  53  108  163  596  658  713  768  627  682  737  407  469  524  579  438  493  548

 367  226  281  343  202  257  312  192  51  106  168  27  82  137  766  625  680  742  601  656  711  577  436  491  553  412  467  522

 341  200  255  310  365  231  286  166  25  80  135  190  56  111  740  599  654  709  764  630  685  551  410  465  520  575  441  496

 315  370  229  284  339  198  253  140  195  54  109  164  23  78  714  769  628  683  738  597  652  525  580  439  494  549  408  463

 282  337  203  258  313  368  227  107  162  28  83  138  193  52  681  736  602  657  712  767  626  492  547  413  468  523  578  437

 256  311  366  225  287  342  201  81  136  191  50  112  167  26  655  710  765  624  686  741  600  466  521  576  435  497  552  411

 230  285  340  199  254  309  371  55  110  165  24  79  134  196  629  684  739  598  653  708  770  440  495  550  409  464  519  581

 400  462  517  572  431  486  541  603  665  720  775  634  689  744  1  63  118  173  32  87  142  218  280  335  390  249  304  359

 570  429  484  546  405  460  515  773  632  687  749  608  663  718  171  30  85  147  6  61  116  388  247  302  364  223  278  333

 544  403  458  513  568  434  489  747  606  661  716  771  637  692  145  4  59  114  169  35  90  362  221  276  331  386  252  307

 518  573  432  487  542  401  456  721  776  635  690  745  604  659  119  174  33  88  143  2  57  336  391  250  305  360  219  274

 485  540  406  461  516  571  430  688  743  609  664  719  774  633  86  141  7  62  117  172  31  303  358  224  279  334  389  248

 459  514  569  428  490  545  404  662  717  772  631  693  748  607  60  115  170  29  91  146  5  277  332  387  246  308  363  222

 433  488  543  402  457  512  574  636  691  746  605  660  715  777  34  89  144  3  58  113  175  251  306  361  220  275  330  392

 

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

Диагональные ортогональные латинские квадраты очень хороши тем, что они сразу пригодны для построения магического квадрата, их не надо преобразовывать в отличие от не диагональных ортогональных латинских квадратов. Однако построить пару диагональных ОЛК сложнее, чем пару не диагональных ОЛК. По крайней мере, я пока не знаю общих методов построения пар диагональных ОЛК, кроме представленного здесь метода составных квадратов. Приведу такой пример: не диагональные ортогональные латинские квадраты 10-го порядка были построены Паркером в 1958 году, а пары диагональных ОЛК 10-го порядка были найдены только в 1992 году. Вполне возможно, что сейчас уже разработаны методы построения пар диагональных ОЛК любого порядка (кроме 2, 3 и 6). Ищите, уважаемые читатели. Да не забудьте мне рассказать, если что-нибудь найдёте.

 

Н. Макарова

 

13 января 2009 г.

г. Саратов

 

       Пишите мне!

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

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