Geum.ru

Автор: Мершиев Александр Владимирович

Вид материалаЛитература

Содержание


Латинские квадраты
V. применение магических и латинских квадратов
Подобный материал:
1   2   3   4   5
2. В левом верхнем квадрате порядка 5 выделить 3 группы клеток, пометив их знаками + (голубой цвет), - (желтый цвет) и * (розовый цвет) соответственно. В каждой строке и каждом столбце нужно выделить по 2 [10=2*5=2*(2*2+1)] клетки первой группы. Их можно расставить по главной диагонали и на ломаной1 диагонали. Клеток второго и третьего типа надо выделить по одной в каждой строке и каждом столбце. В качестве клеток второй и третьей групп можно взять клетки, расположенные на двух других ломаных диагоналях.

3. Для клеток первой группы находим симметричные клетки относительно вертикальной оси, помечаем их тоже знаком + (голубой цвет), т. е. клеток, отмеченных знаком + (голубых) будет 10.


1 Ломаной называется диагональ, которая, дойдя до края квадрата, продолжается параллельно первому отрезку от противоположного края, такую диагональ образуют заштрихованные клетки.



100
99
3
4
5
6
7
8
92
91

11
89
88
14
15
16
17
83
82
20

21
22
78
77
25
26
74
73
29
30

31
32
33
67
66
65
64
38
39
40

60
42
43
44
56
55
47
48
49
51

50
52
53
54
46
45
57
58
59
41

61
62
63
37
36
35
34
68
69
70

71
72
28
27
75
76
24
23
79
80

81
19
18
84
85
86
87
13
12
90

10
9
93
94
95
96
97
98
2
1
4). Содержимое каждой таких отмеченных клеток обмениваем с содержимым соответствующей ей центрально-симметричной клетки.


.



100
99
93
4
5
6
7
8
92
91

11
89
88
84
16
15
17
83
82
20

21
22
78
77
75
26
74
73
29
30

61
32
33
67
66
65
64
38
39
40

60
52
43
44
56
55
47
48
49
51

50
42
53
54
46
45
57
58
59
41

31
62
63
37
36
35
34
68
69
70

71
72
28
27
25
76
24
23
79
80

81
19
18
14
85
86
87
13
12
90

10
9
3
94
95
96
97
98
2
1
4. Содержимое каждой из 5 клеток, отмеченных знаком минус (желтый цвет), обмениваем с содержимым симметричной относительно горизонтальной оси клетки.



100
99
93
7
5
6
4
8
92
91

11
89
88
84
16
15
17
83
82
20

30
22
78
77
75
26
74
73
29
21

61
39
33
67
66
65
64
38
32
40

60
52
48
44
56
55
47
43
49
51

50
42
53
54
46
45
57
58
59
41

31
62
63
37
36
35
34
68
69
70

71
72
28
27
25
76
24
23
79
80

81
19
18
14
85
86
87
13
12
90

10
9
3
94
95
96
97
98
2
1



5. Содержимое каждой из 5клеток третьей группы, отмеченной * (розовый цвет) обмениваем с содержимым симметричной относительно вертикальной оси клетки.

После этих перестановок получится четно-нечетный магический квадрат с суммой, равной 505.


IV. ЛАТИНСКИЕ КВАДРАТЫ

Латинским квадратом называется квадрат n*n клеток, в которых написаны числа от 1, до n, притом так, что в каждой строке и каждом столбце встречаются все эти числа по одному разу. На рис.3 изображены два таких квадрата3*3. Они обладают интересной особенностью: если один квадрат наложить на другой, то все пары получившихся чисел оказываются различными (рис.5). Такие пары латинских квадратов называются ортогональными.


1
2
3

3
1
2

2
3
1

1
2
3

2
3
1

3
1
2

1 1
2 2
3 3

2 3
3 1
1 2

3 2
1 3
2 1



Рис.5

Впервые задачу отыскания ортогональных латинских квадратов поставил Л. Эйлер, причём в такой занимательной формулировке: «Среди 36 офицеров поровну уланов, драгунов, гусаров, кирасиров, кавалергардов и гренадеров и, кроме того, поровну генералов, полковников, майоров, капитанов, поручиков и подпоручиков, причем каждый род войск представлен офицерами всех шести рангов. Можно ли выстроить всех офицеров в каре 6 * 6 так, чтобы в любой колонне и любой шеренге встречались офицеры всех рангов?»

Эйлер не смог найти решения этой задачи. В 1901 г. было доказано, что ортогональных квадратов 6*6 не существует. В 1959 г. помощью ЭВМ были найдены сначала ортогональные квадраты 10*10, потом 14*14, 18 *18, 22 *22. А затем было показано, что для любого n , кроме 6, существуют ортогональные квадраты n *n.





V. ПРИМЕНЕНИЕ МАГИЧЕСКИХ И ЛАТИНСКИХ КВАДРАТОВ


1. Шифрование текстов

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

Пример магического квадрата и его заполнения сообщением показан на рисунке 6.


16
3
2
13

5
10
11
8

9
6
7
12

4
15
14
1

О
И
Р
М

Е
О
С
Ю

В
Т
А
Ь

Л
Г
О
П