Н. Макарова

 

ПОСТРОЕНИЕ ГРУППЫ MOLS ДВЕНАДЦАТОГО ПОРЯДКА

 

Построение пар ОЛК 12-го порядка уже было показано. Смотрите, например, статью: http://www.natalimak1.narod.ru/grolk.htm (рис. 11 - 12). Я построила пары ОЛК данного порядка двумя способами: 1) методом составных квадратов; 2) по алгоритму для порядков серии n = 6k, k = 2, 3, 4, …

Теперь хочу показать построение группы взаимно ортогональных латинских квадратов (MOLS), состоящей из 5 квадратов. Это построение придумали авторы: Дюльмаж, Джонсон и Мендельсон. Оно основано на применении абелевой группы и описано в книге М. Холла “Комбинаторика” (М.: Мир, 1970). По этой книге здесь и приводится построение данной группы MOLS.

Приведу цитату из книги, чтобы читатели видели наглядно описание, приведённое автором (стр. 281 – 282).

 

“Обозначим  ai = ai, i = 0, …, 5, bi = bai, i = 0, …, 5.

Построим пять строк:

 

a0  a1  a2  a3  a4  a5  b0  b1  b2  b3  b4  b5

a0  b0  b2  a2  b1  a1  b3  b5  a4  b4  a5  a3

a0  a3  b0  a1  b3  b5  a2  b2  a5  a4  b1  b4

a0  b2  a1  b5  a5  b3  a3  b4  a2  b1  b0  a4

a0  a4  b5  b4  a2  b1  b2  b0  b3  a1  a3  a5

 

Возьмём эти строки в качестве первых строк пяти квадратов. Строки со второй по двенадцатую образуются умножением первых строк соответственно на a1, …, a5, b0, …, b5. Нет никакого другого квадрата порядка 12, ортогонального ко всем этим квадратам, и не было найдено никакого множества из шести попарно ортогональных квадратов порядка 12”.

Это всё описание построение, приведённое в книге. Не сразу мне удалось разобраться с этим построением, помогли на форуме http://dxdy.ru/topic12959.html , подсказав, как выполняется умножение элементов абелевой группы 12-го порядка, являющейся прямым произведением циклических групп порядков 6 и 2. Итак, имеем следующие правила умножения элементов:

 

akbp * ambn = ak+m * bp+n

 

при этом (k+m) берётся по модулю 6, а (p+n) – по модулю 2.

Далее: a6 = a0 = 1, b2 = b0 = 1.

Например, a2b * a5 = a * b.

 

Теперь всё готово для построения группы из пяти латинских квадратов, заполненных выражениями вида aibj (i = 0, 1, … 5, j = 0, 1). В рассматриваемой абелевой группе 12-го порядка будет ровно 12 различных выражений данного вида, а именно:

 

1, a, a2, a3, a4, a5, b, ba, ba2, ba3, ba4, ba5.

 

После того, как все пять латинских квадратов будут заполнены приведёнными выражениями (заполнение квадратов выполняется по описанию, приведённому в книге Холла), надо во всех квадратах заменить символьные выражения на числа от 2 до 12, причём во всех квадратах одинаково. При этом выбор чисел для выражений может быть совершенно произвольным. Я выбрала такие значения для символьных выражений:

 

a = 2, a2 = 3, a3 = 4, a4 = 5, a5 = 6, b = 7, ba = 8, ba2 = 9, ba3 = 10, ba4 = 11, ba5 = 12.

 

Я покажу только один латинский квадрат, заполненный символьными выражениями – первый (рис. 1). Остальные четыре квадрата читатели построят самостоятельно, здесь будут показаны латинские квадраты, заполненные числами.

 

1

a

a2

a3

a4

a5

b

ba

ba2

ba3

ba4

ba5

a

a2

a3

a4

a5

1

ba

ba2

ba3

ba4

ba5

b

a2

a3

a4

a5

1

a

ba2

ba3

ba4

ba5

b

ba

a3

a4

a5

1

a

a2

ba3

ba4

ba5

b

ba

ba2

a4

a5

1

a

a2

a3

ba4

ba5

b

ba

ba2

ba3

a5

1

a

a2

a3

a4

ba5

b

ba

ba2

ba3

ba4

b

ba

ba2

ba3

ba4

ba5

1

a

a2

a3

a4

a5

ba

ba2

ba3

ba4

ba5

b

a

a2

a3

a4

a5

1

ba2

ba3

ba4

ba5

b

ba

a2

a3

a4

a5

1

a

ba3

ba4

ba5

b

ba

ba2

a3

a4

a5

1

a

a2

ba4

ba5

b

ba

ba2

ba3

a4

a5

1

a

a2

a3

ba5

b

ba

ba2

ba3

ba4

a5

1

a

a2

a3

a4

 

Рис. 1

 

Очень интересная закономерность построения квадрата.

Теперь показываю все пять латинских квадратов группы, заполненные числами (рис. 2 – 6).

Замечание: здесь латинские квадраты заполняются числами от 1 до 12. Для перехода к традиционной форме записи латинских квадратов (заполненных числами от 0 до 11) надо все элементы в квадратах уменьшить на единицу.

 

Первый латинский квадрат (соответствует квадрату с рис. 1)

 

1

2

3

4

5

6

7

8

9

10

11

12

2

3

4

5

6

1

8

9

10

11

12

7

3

4

5

6

1

2

9

10

11

12

7

8

4

5

6

1

2

3

10

11

12

7

8

9

5

6

1

2

3

4

11

12

7

8

9

10

6

1

2

3

4

5

12

7

8

9

10

11

7

8

9

10

11

12

1

2

3

4

5

6

8

9

10

11

12

7

2

3

4

5

6

1

9

10

11

12

7

8

3

4

5

6

1

2

10

11

12

7

8

9

4

5

6

1

2

3

11

12

7

8

9

10

5

6

1

2

3

4

12

7

8

9

10

11

6

1

2

3

4

5

 

Рис. 2

 

Второй латинский квадрат

 

1

7

9

3

8

2

10

12

5

11

6

4

2

8

10

4

9

3

11

7

6

12

1

5

3

9

11

5

10

4

12

8

1

7

2

6

4

10

12

6

11

5

7

9

2

8

3

1

5

11

7

1

12

6

8

10

3

9

4

2

6

12

8

2

7

1

9

11

4

10

5

3

7

1

3

9

2

8

4

6

11

5

12

10

8

2

4

10

3

9

5

1

12

6

7

11

9

3

5

11

4

10

6

2

7

1

8

12

10

4

6

12

5

11

1

3

8

2

9

7

11

5

1

7

6

12

2

4

9

3

10

8

12

6

2

8

1

7

3

5

10

4

11

9

 

Рис. 3

 

Третий латинский квадрат

 

1

4

7

2

10

12

3

9

6

5

8

11

2

5

8

3

11

7

4

10

1

6

9

12

3

6

9

4

12

8

5

11

2

1

10

7

4

1

10

5

7

9

6

12

3

2

11

8

5

2

11

6

8

10

1

7

4

3

12

9

6

3

12

1

9

11

2

8

5

4

7

10

7

10

1

8

4

6

9

3

12

11

2

5

8

11

2

9

5

1

10

4

7

12

3

6

9

12

3

10

6

2

11

5

8

7

4

1

10

7

4

11

1

3

12

6

9

8

5

2

11

8

5

12

2

4

7

1

10

9

6

3

12

9

6

7

3

5

8

2

11

10

1

4

 

Рис. 4

 

Четвёртый латинский квадрат

 

1

9

2

12

6

10

4

11

3

8

7

5

2

10

3

7

1

11

5

12

4

9

8

6

3

11

4

8

2

12

6

7

5

10

9

1

4

12

5

9

3

7

1

8

6

11

10

2

5

7

6

10

4

8

2

9

1

12

11

3

6

8

1

11

5

9

3

10

2

7

12

4

7

3

8

6

12

4

10

5

9

2

1

11

8

4

9

1

7

5

11

6

10

3

2

12

9

5

10

2

8

6

12

1

11

4

3

7

10

6

11

3

9

1

7

2

12

5

4

8

11

1

12

4

10

2

8

3

7

6

5

9

12

2

7

5

11

3

9

4

8

1

6

10

 

Рис. 5

 

Пятый латинский квадрат

 

1

5

12

11

3

8

9

7

10

2

4

6

2

6

7

12

4

9

10

8

11

3

5

1

3

1

8

7

5

10

11

9

12

4

6

2

4

2

9

8

6

11

12

10

7

5

1

3

5

3

10

9

1

12

7

11

8

6

2

4

6

4

11

10

2

7

8

12

9

1

3

5

7

11

6

5

9

2

3

1

4

8

10

12

8

12

1

6

10

3

4

2

5

9

11

7

9

7

2

1

11

4

5

3

6

10

12

8

10

8

3

2

12

5

6

4

1

11

7

9

11

9

4

3

7

6

1

5

2

12

8

10

12

10

5

4

8

1

2

6

3

7

9

11

 

Рис. 6

 

Легко видеть, что все квадраты группы не диагональные. Понятно, что из пяти квадратов группы можно составить 10 пар ортогональных латинских квадратов. Возьмём, например, пару, состоящую из второго и третьего квадратов. В этой паре один из квадратов (третий) оказался уже нетрадиционным магическим квадратом с магической константой 78, то есть его не надо преобразовывать, он уже имеет нужную сумму в диагоналях. Второй латинский квадрат очень легко преобразовывается в нетрадиционный магический квадрат такой заменой: 1 à 3, 3 à1. Получив пару ортогональных латинских квадратов, каждый из которых является нетрадиционным магическим квадратом с магической константой 78, мы можем построить два магических квадрата 12-го порядка (при построении магических квадратов по известной формуле надо привести латинские квадраты к традиционной форме записи, или можно оставить квадраты как есть, но изменить формулу для построения магического квадрата). На рис. 7 показан один из магических квадратов 12-го порядка, построенный из данной пары ОЛК.

 

25

76

103

2

94

24

111

141

54

125

68

47

14

89

116

39

107

7

124

82

61

138

33

60

3

102

129

52

120

44

137

95

26

73

22

67

40

109

142

65

127

57

78

108

15

86

11

32

53

122

83

30

140

70

85

115

4

99

48

21

66

135

96

13

81

35

98

128

41

112

55

10

79

34

1

104

16

90

45

63

132

59

134

113

92

23

38

117

5

97

58

28

139

72

75

126

105

12

51

130

42

110

71

17

80

31

88

133

118

43

64

143

49

123

36

6

93

20

101

74

131

56

29

84

62

136

19

37

106

9

114

87

144

69

18

91

27

77

8

50

119

46

121

100

 

Рис. 7

 

В квадрате выделена начальная цепочка. Нельзя сказать, что она имеет какую-то определённую форму.

Итак, мы имеем ещё один магический квадрат 12-го порядка, построенный из пары классических ортогональных латинских квадратов методом латинских квадратов (первый такой квадрат я построила в одной из ранних статей цикла “Новые аспекты метода латинских квадратов”).

 

***

 

            Нашла ещё одну статью тех же авторов, которые придумали построение   группы MOLS 12-го порядка с помощью абелевой группы. Статья называется “Orthomorphisms of groups and orthogonal Latin squares” (D. M. Jonson и другие). В этой статье ничего не поняла, но увидела картинку, которая очень похожа на латинский квадрат 12-го порядка. Взяла эту картинку и построила из неё очень интересную пару ортогональных латинских квадратов. Сначала покажу копию картинки (рис. 8):

 

                                                 

 

Рис. 8

 

По этой картинке я построила такой латинский квадрат (рис. 9):

0

5

4

3

2

1

11

6

7

8

9

10

1

0

5

4

3

2

10

11

6

7

8

9

2

1

0

5

4

3

9

10

11

6

7

8

3

2

1

0

5

4

8

9

10

11

6

7

4

3

2

1

0

5

7

8

9

10

11

6

5

4

3

2

1

0

6

7

8

9

10

11

11

6

7

8

9

10

0

5

4

3

2

1

10

11

6

7

8

9

1

0

5

4

3

2

9

10

11

6

7

8

2

1

0

5

4

3

8

9

10

11

6

7

3

2

1

0

5

4

7

8

9

10

11

6

4

3

2

1

0

5

6

7

8

9

10

11

5

4

3

2

1

0

 

Рис. 9

 

       Совершенно не представляя, как строить второй латинский квадрат ортогональный данному, я провела эксперимент: переставила строки в этом латинском квадрате так, чтобы главная диагональ, состоящая из нулей, превратилась в диагональ, содержащую перестановку чисел 0, 1, 2, … , 11. Эксперимент удался! Я получила латинский квадрат ортогональный данному. Смотрите этот квадрат на рис. 10.

 

9

10

11

6

7

8

2

1

0

5

4

3

6

7

8

9

10

11

5

4

3

2

1

0

4

3

2

1

0

5

7

8

9

10

11

6

1

0

5

4

3

2

10

11

6

7

8

9

3

2

1

0

5

4

8

9

10

11

6

7

7

8

9

10

11

6

4

3

2

1

0

5

8

9

10

11

6

7

3

2

1

0

5

4

10

11

6

7

8

9

1

0

5

4

3

2

2

1

0

5

4

3

9

10

11

6

7

8

0

5

4

3

2

1

11

6

7

8

9

10

5

4

3

2

1

0

6

7

8

9

10

11

11

6

7

8

9

10

0

5

4

3

2

1

 

Рис. 10

 

    Уникальность этой пары ОЛК состоит в том, что второй латинский квадрат получен из первого перестановкой строк. В одной из ранних статей цикла “Новые аспекты метода латинских квадратов” была показана пара ОЛК 10-го порядка (найдена в Интернете, автор Лямзин), в которой тоже второй латинский квадрат получается из первого перестановкой строк. Существует ли аналогичная пара ОЛК 14-го порядка? Интересный         вопрос. Кстати, я начала писать программу для решения этой задачи, но почему-то забросила её. Надо будет вернуться к ней.

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

 А полумагический квадрат 12-го порядка из данной пары ОЛК можно построить сразу. Вот с какой оригинальной начальной цепочкой получается этот квадрат (рис. 11):

 

10

71

60

43

32

21

135

74

85

102

113

124

19

8

69

58

47

36

126

137

76

87

98

109

29

16

3

62

49

42

116

129

142

83

96

103

38

25

18

5

64

51

107

120

127

140

81

94

52

39

26

13

6

65

93

106

119

132

139

80

68

57

46

35

24

7

77

88

99

110

121

138

141

82

95

108

115

128

4

63

50

37

30

17

131

144

79

92

105

118

14

1

66

53

40

27

111

122

133

78

89

100

34

23

12

67

56

45

97

114

125

136

75

86

48

31

20

9

70

59

90

101

112

123

134

73

55

44

33

22

11

72

84

91

104

117

130

143

61

54

41

28

15

2

 

Рис. 11

 

    Если латинские квадраты поменять местами, получится такой полумагический квадрат (рис. 12):

 

109

126

137

76

87

98

36

19

8

69

58

47

74

85

102

113

124

135

71

60

43

32

21

10

51

38

25

18

5

64

94

107

120

127

140

81

16

3

62

49

42

29

129

142

83

96

103

116

41

28

15

2

61

54

104

117

130

143

84

91

90

101

112

123

134

73

55

44

33

22

11

72

108

115

128

141

82

95

37

30

17

4

63

50

131

144

79

92

105

118

14

1

66

53

40

27

34

23

12

67

56

45

111

122

133

78

89

100

9

70

59

48

31

20

136

75

86

97

114

125

68

57

46

35

24

7

77

88

99

110

121

138

139

80

93

106

119

132

6

65

52

39

26

13

 

Рис. 12

 

      А теперь покажу ещё один приём, хотя он уже был показан в одной из статей данного цикла. Берём полумагический квадрат с рис. 12 и вводим его в программу перестановки строк, которая выполняет перестановку строк до тех пор, пока не получится магический квадрат. Программа трудилась не очень долго, всего около минуты, магический квадрат построен. Вы видите его на рис. 13.

 

109

126

137

76

87

98

36

19

8

69

58

47

74

85

102

113

124

135

71

60

43

32

21

10

41

28

15

2

61

54

104

117

130

143

84

91

9

70

59

48

31

20

136

75

86

97

114

125

131

144

79

92

105

118

14

1

66

53

40

27

16

3

62

49

42

29

129

142

83

96

103

116

90

101

112

123

134

73

55

44

33

22

11

72

108

115

128

141

82

95

37

30

17

4

63

50

34

23

12

67

56

45

111

122

133

78

89

100

51

38

25

18

5

64

94

107

120

127

140

81

68

57

46

35

24

7

77

88

99

110

121

138

139

80

93

106

119

132

6

65

52

39

26

13

 

Рис. 13

 

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

 

9

10

11

6

7

8

2

1

0

5

4

3

 

0

5

4

3

2

1

11

6

7

8

9

10

6

7

8

9

10

11

5

4

3

2

1

0

1

0

5

4

3

2

10

11

6

7

8

9

3

2

1

0

5

4

8

9

10

11

6

7

4

3

2

1

0

5

7

8

9

10

11

6

0

5

4

3

2

1

11

6

7

8

9

10

8

9

10

11

6

7

3

2

1

0

5

4

10

11

6

7

8

9

1

0

5

4

3

2

10

11

6

7

8

9

1

0

5

4

3

2

1

0

5

4

3

2

10

11

6

7

8

9

3

2

1

0

5

4

8

9

10

11

6

7

7

8

9

10

11

6

4

3

2

1

0

5

5

4

3

2

1

0

6

7

8

9

10

11

8

9

10

11

6

7

3

2

1

0

5

4

11

6

7

8

9

10

0

5

4

3

2

1

2

1

0

5

4

3

9

10

11

6

7

8

9

10

11

6

7

8

2

1

0

5

4

3

4

3

2

1

0

5

7

8

9

10

11

6

2

1

0

5

4

3

9

10

11

6

7

8

5

4

3

2

1

0

6

7

8

9

10

11

7

8

9

10

11

6

4

3

2

1

0

5

11

6

7

8

9

10

0

5

4

3

2

1

6

7

8

9

10

11

5

4

3

2

1

0

 

Рис. 14

 

    Случай очень интересный: латинские квадраты в этой паре ОЛК не являются нетрадиционными магическими квадратами с магической константой 66. В них есть магическая сумма чисел только в одной главной диагонали одного и того же направления. Тем не менее, из этой пары получается магический квадрат. Дело в том, что суммы чисел S1 и S2 в других главных диагоналях удовлетворяют равенству:

 

12*S1 + S2 + 12 = 870        (S1 = 68, S2 = 42)

 

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

Такой же приём можно применить и ко второму магическому квадрату с рис. 11. Попробуйте!

 

 

 

 

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

 

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

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

 

 

24 февраля – 15 марта 2009 г.

г. Саратов

 

       Пишите мне!

Рейтинг@Mail.ru

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

 



Hosted by uCoz