Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Цитата: evatutin от 01.06.2020, 21:34Покажем, что не симметричных двушек (структур типа линия-3 или, что то же самое, — звезда 1:2) также с легкостью можно подобрать CMS, отображающие лучи друг в друга, а центральная квадрат — сам в себя. Для этого возьмем ничем не примечательную двушку A—B—C с характеристикой ортогональности = 12 (таких у нас абсолютное большинство):
B = 0123456789120436985727869351048057192346386957142059710486327648213095453062791894157802636392804571 (центральный квадрат)
A = 0123456789965201743852783490163819524607190526837460347825914391875260748693012585671039422740691853 (луч 1)
C = 0123456789965281743052703498163819524607198526037460347825914391075268740693812585671039422748691053 (луч 2)и организуем для нее поиск CMS. Оказывается, что соответствующих CMS находится несколько тысяч (дальше поиск просто был прерван). Некоторые из найденных CMS представлены ниже:
1 CMS:
0 6 5 7 4 2 1 3 8 9
74 32 67 81 19 82 24 17 48 14
44 66 30 27 16 60 87 23 73 96
22 31 11 58 90 43 71 84 38 99
45 41 46 35 20 40 42 70 18 49
59 51 91 88 86 55 79 78 33 50
25 65 62 94 69 61 21 12 77 64
47 36 76 28 10 83 72 68 57 56
80 13 15 75 37 85 54 26 53 98
34 52 92 97 63 95 29 93 89 39Loops structure: {1:16, 2:42}
2 CMS:
0 6 5 7 4 2 1 58 8 24
61 32 67 81 19 82 9 17 48 14
44 66 41 27 16 60 75 23 73 96
22 31 11 3 90 43 71 84 38 10
45 30 46 35 20 40 42 70 26 49
59 51 91 88 95 55 79 78 52 50
25 65 47 94 69 74 21 12 77 64
62 36 76 28 99 83 72 68 57 56
80 13 15 87 37 85 54 18 53 98
34 33 92 97 63 86 29 93 89 39Loops structure: {1:12, 2:29, 3:4, 6:3}
3 CMS:
0 6 5 7 4 2 10 3 8 77
15 26 67 81 19 82 24 17 48 14
44 66 30 27 16 60 59 23 73 62
22 31 11 40 90 43 71 33 38 99
45 63 46 35 20 58 42 70 18 49
87 51 91 88 86 55 79 78 84 50
25 65 96 94 69 61 21 12 9 64
47 36 76 95 1 83 72 68 57 56
80 13 74 75 37 85 54 32 53 98
34 52 92 97 41 28 29 93 89 39Loops structure: {1:12, 2:29, 3:4, 6:3}
4 CMS:
0 6 5 7 4 2 10 40 8 24
61 26 67 81 19 82 77 17 48 14
44 66 63 27 16 60 75 23 73 62
22 31 11 3 90 43 71 33 38 1
45 30 46 35 20 58 42 70 32 49
87 51 91 88 28 55 79 78 52 50
25 65 47 94 69 15 21 12 9 64
96 36 76 95 99 83 72 68 57 56
80 13 74 59 37 85 54 18 53 98
34 84 92 97 41 86 29 93 89 39Loops structure: {1:12, 2:19, 5:4, 10:3}
5 CMS:
0 6 5 7 4 2 99 40 8 9
74 18 67 81 19 82 77 17 48 14
44 66 63 27 16 60 87 23 73 47
22 31 11 58 90 43 71 52 38 1
45 41 46 35 20 3 42 70 32 49
75 51 91 88 28 55 79 78 33 50
25 65 62 94 69 15 21 12 24 64
96 36 76 86 10 83 72 68 57 56
80 13 61 59 37 85 54 26 53 98
34 84 92 97 30 95 29 93 89 39Loops structure: {1:16, 2:22, 4:10}
6 CMS:
0 6 5 7 4 2 99 58 8 77
15 18 67 81 19 82 9 17 48 14
44 66 41 27 16 60 59 23 73 47
22 31 11 40 90 43 71 52 38 10
45 63 46 35 20 3 42 70 26 49
75 51 91 88 95 55 79 78 84 50
25 65 96 94 69 74 21 12 24 64
62 36 76 86 1 83 72 68 57 56
80 13 61 87 37 85 54 32 53 98
34 33 92 97 30 28 29 93 89 39Loops structure: {1:12, 2:19, 5:4, 10:3}
7 CMS:
0 6 5 7 4 59 10 3 8 35
90 26 28 81 19 82 24 17 48 14
32 66 30 27 16 60 2 23 73 62
22 31 11 89 15 43 71 33 38 99
45 56 46 77 20 58 42 70 18 49
87 51 91 88 86 55 79 1 21 50
25 65 13 94 69 61 84 12 9 64
47 36 76 95 78 83 72 68 57 63
80 96 74 75 37 85 54 44 53 98
34 52 92 97 41 67 29 93 40 39Loops structure: {1:12, 2:19, 5:4, 10:3}
8 CMS:
0 6 5 7 4 59 10 89 8 24
61 26 28 81 19 82 35 17 48 14
32 66 56 27 16 60 75 23 73 62
22 31 11 3 15 43 71 33 38 78
45 30 46 77 20 58 42 70 44 49
87 51 91 88 67 55 79 1 52 50
25 65 47 94 69 90 84 12 9 64
13 36 76 95 99 83 72 68 57 63
80 96 74 2 37 85 54 18 53 98
34 21 92 97 41 86 29 93 40 39Loops structure: {1:12, 2:9, 7:4, 14:3}
9 CMS:
0 6 5 7 4 59 78 3 8 9
74 44 28 81 19 82 24 17 48 14
32 66 30 27 16 60 87 23 73 13
22 31 11 58 15 43 71 21 38 99
45 41 46 77 20 89 42 70 18 49
2 51 91 88 86 55 79 1 33 50
25 65 62 94 69 61 84 12 35 64
47 36 76 67 10 83 72 68 57 63
80 96 90 75 37 85 54 26 53 98
34 52 92 97 56 95 29 93 40 39Loops structure: {1:16, 2:22, 4:10}
10 CMS:
0 6 5 7 4 59 78 58 8 24
61 44 28 81 19 82 9 17 48 14
32 66 41 27 16 60 75 23 73 13
22 31 11 3 15 43 71 21 38 10
45 30 46 77 20 89 42 70 26 49
2 51 91 88 95 55 79 1 52 50
25 65 47 94 69 74 84 12 35 64
62 36 76 67 99 83 72 68 57 63
80 96 90 87 37 85 54 18 53 98
34 33 92 97 56 86 29 93 40 39Loops structure: {1:12, 2:9, 3:4, 4:10, 6:3}
...
Если в качестве исходных квадратов взять просто 3 случайных квадрата, то для них CMS не находится, т.к. не существует, т.е. найденное свойство не является простой случайностью, а представляет собой следствие определенной закономерности...
Покажем, что не симметричных двушек (структур типа линия-3 или, что то же самое, — звезда 1:2) также с легкостью можно подобрать CMS, отображающие лучи друг в друга, а центральная квадрат — сам в себя. Для этого возьмем ничем не примечательную двушку A—B—C с характеристикой ортогональности = 12 (таких у нас абсолютное большинство):
B = 0123456789120436985727869351048057192346386957142059710486327648213095453062791894157802636392804571 (центральный квадрат)
A = 0123456789965201743852783490163819524607190526837460347825914391875260748693012585671039422740691853 (луч 1)
C = 0123456789965281743052703498163819524607198526037460347825914391075268740693812585671039422748691053 (луч 2)
и организуем для нее поиск CMS. Оказывается, что соответствующих CMS находится несколько тысяч (дальше поиск просто был прерван). Некоторые из найденных CMS представлены ниже:
1 CMS:
0 6 5 7 4 2 1 3 8 9
74 32 67 81 19 82 24 17 48 14
44 66 30 27 16 60 87 23 73 96
22 31 11 58 90 43 71 84 38 99
45 41 46 35 20 40 42 70 18 49
59 51 91 88 86 55 79 78 33 50
25 65 62 94 69 61 21 12 77 64
47 36 76 28 10 83 72 68 57 56
80 13 15 75 37 85 54 26 53 98
34 52 92 97 63 95 29 93 89 39
Loops structure: {1:16, 2:42}
2 CMS:
0 6 5 7 4 2 1 58 8 24
61 32 67 81 19 82 9 17 48 14
44 66 41 27 16 60 75 23 73 96
22 31 11 3 90 43 71 84 38 10
45 30 46 35 20 40 42 70 26 49
59 51 91 88 95 55 79 78 52 50
25 65 47 94 69 74 21 12 77 64
62 36 76 28 99 83 72 68 57 56
80 13 15 87 37 85 54 18 53 98
34 33 92 97 63 86 29 93 89 39
Loops structure: {1:12, 2:29, 3:4, 6:3}
3 CMS:
0 6 5 7 4 2 10 3 8 77
15 26 67 81 19 82 24 17 48 14
44 66 30 27 16 60 59 23 73 62
22 31 11 40 90 43 71 33 38 99
45 63 46 35 20 58 42 70 18 49
87 51 91 88 86 55 79 78 84 50
25 65 96 94 69 61 21 12 9 64
47 36 76 95 1 83 72 68 57 56
80 13 74 75 37 85 54 32 53 98
34 52 92 97 41 28 29 93 89 39
Loops structure: {1:12, 2:29, 3:4, 6:3}
4 CMS:
0 6 5 7 4 2 10 40 8 24
61 26 67 81 19 82 77 17 48 14
44 66 63 27 16 60 75 23 73 62
22 31 11 3 90 43 71 33 38 1
45 30 46 35 20 58 42 70 32 49
87 51 91 88 28 55 79 78 52 50
25 65 47 94 69 15 21 12 9 64
96 36 76 95 99 83 72 68 57 56
80 13 74 59 37 85 54 18 53 98
34 84 92 97 41 86 29 93 89 39
Loops structure: {1:12, 2:19, 5:4, 10:3}
5 CMS:
0 6 5 7 4 2 99 40 8 9
74 18 67 81 19 82 77 17 48 14
44 66 63 27 16 60 87 23 73 47
22 31 11 58 90 43 71 52 38 1
45 41 46 35 20 3 42 70 32 49
75 51 91 88 28 55 79 78 33 50
25 65 62 94 69 15 21 12 24 64
96 36 76 86 10 83 72 68 57 56
80 13 61 59 37 85 54 26 53 98
34 84 92 97 30 95 29 93 89 39
Loops structure: {1:16, 2:22, 4:10}
6 CMS:
0 6 5 7 4 2 99 58 8 77
15 18 67 81 19 82 9 17 48 14
44 66 41 27 16 60 59 23 73 47
22 31 11 40 90 43 71 52 38 10
45 63 46 35 20 3 42 70 26 49
75 51 91 88 95 55 79 78 84 50
25 65 96 94 69 74 21 12 24 64
62 36 76 86 1 83 72 68 57 56
80 13 61 87 37 85 54 32 53 98
34 33 92 97 30 28 29 93 89 39
Loops structure: {1:12, 2:19, 5:4, 10:3}
7 CMS:
0 6 5 7 4 59 10 3 8 35
90 26 28 81 19 82 24 17 48 14
32 66 30 27 16 60 2 23 73 62
22 31 11 89 15 43 71 33 38 99
45 56 46 77 20 58 42 70 18 49
87 51 91 88 86 55 79 1 21 50
25 65 13 94 69 61 84 12 9 64
47 36 76 95 78 83 72 68 57 63
80 96 74 75 37 85 54 44 53 98
34 52 92 97 41 67 29 93 40 39
Loops structure: {1:12, 2:19, 5:4, 10:3}
8 CMS:
0 6 5 7 4 59 10 89 8 24
61 26 28 81 19 82 35 17 48 14
32 66 56 27 16 60 75 23 73 62
22 31 11 3 15 43 71 33 38 78
45 30 46 77 20 58 42 70 44 49
87 51 91 88 67 55 79 1 52 50
25 65 47 94 69 90 84 12 9 64
13 36 76 95 99 83 72 68 57 63
80 96 74 2 37 85 54 18 53 98
34 21 92 97 41 86 29 93 40 39
Loops structure: {1:12, 2:9, 7:4, 14:3}
9 CMS:
0 6 5 7 4 59 78 3 8 9
74 44 28 81 19 82 24 17 48 14
32 66 30 27 16 60 87 23 73 13
22 31 11 58 15 43 71 21 38 99
45 41 46 77 20 89 42 70 18 49
2 51 91 88 86 55 79 1 33 50
25 65 62 94 69 61 84 12 35 64
47 36 76 67 10 83 72 68 57 63
80 96 90 75 37 85 54 26 53 98
34 52 92 97 56 95 29 93 40 39
Loops structure: {1:16, 2:22, 4:10}
10 CMS:
0 6 5 7 4 59 78 58 8 24
61 44 28 81 19 82 9 17 48 14
32 66 41 27 16 60 75 23 73 13
22 31 11 3 15 43 71 21 38 10
45 30 46 77 20 89 42 70 26 49
2 51 91 88 95 55 79 1 52 50
25 65 47 94 69 74 84 12 35 64
62 36 76 67 99 83 72 68 57 63
80 96 90 87 37 85 54 18 53 98
34 33 92 97 56 86 29 93 40 39
Loops structure: {1:12, 2:9, 3:4, 4:10, 6:3}
...
Если в качестве исходных квадратов взять просто 3 случайных квадрата, то для них CMS не находится, т.к. не существует, т.е. найденное свойство не является простой случайностью, а представляет собой следствие определенной закономерности...
Цитата: evatutin от 01.06.2020, 22:49Рассмотрим трешку (структуру типа звезда 1:3) с центральным квадратом A и лучами B1, B2 и B3. Будем искать CMS, попарно отражающие луч Bi в луч Bj с соответствующим отражением центрального квадрата самого в себя. Оказывается, что отражения лучей друг в друга существуют не всегда...
Пример 1
A = 0123456789120467983564903851722578910364895274360198312640573765821490438910752656170329487046598213
B1 = 0428965173869347205112570436989082154736674530128943617985203509817462591023684778346209152176589304
B2 = 0428965173968347205112570436898092154736674530129843617985203509817462591023684778346209152176589304
B3 = 0428765193986347205112570438697082154936694530128743716985203509816472561023974887349206152196587304B1-B2: CMS found
0 1 2 4 3 5 6 7 8 9
10 11 12 60 14 15 16 17 70 19
20 85 22 23 45 25 26 27 28 29
30 31 32 33 34 35 36 92 38 52
40 41 42 43 44 24 88 47 48 49
50 51 39 53 54 81 71 57 58 59
13 61 62 77 96 65 66 99 68 69
18 56 72 73 74 75 76 63 78 79
80 55 82 83 84 21 86 95 46 89
90 91 37 93 94 87 64 97 98 67Loops structure: {1:72, 2:14}
B1-B3: CMS found
0 6 19 3 39 30 1 44 8 16
79 77 12 21 35 76 34 17 99 97
82 88 50 84 24 89 2 81 28 80
5 86 32 72 9 14 57 37 74 4
96 41 43 42 90 45 60 53 48 93
22 33 52 38 63 66 56 36 65 59
85 83 98 54 64 26 55 70 68 91
67 71 51 73 20 69 15 11 94 10
29 27 47 61 23 46 31 87 13 25
7 75 92 49 78 95 40 58 62 18Loops structure: {1:22, 2:24, 3:6, 6:2}
B2-B1: CMS found
0 1 2 4 3 5 6 7 8 9
10 11 12 60 14 15 16 17 70 19
20 85 22 23 45 25 26 27 28 29
30 31 32 33 34 35 36 92 38 52
40 41 42 43 44 24 88 47 48 49
50 51 39 53 54 81 71 57 58 59
13 61 62 77 96 65 66 99 68 69
18 56 72 73 74 75 76 63 78 79
80 55 82 83 84 21 86 95 46 89
90 91 37 93 94 87 64 97 98 67Loops structure: {1:72, 2:14}
B2-B3: CMS found
0 18 9 10 79 39 25 7 77 2
3 87 84 47 89 15 97 31 1 88
72 38 78 23 98 94 21 71 76 95
41 45 32 26 65 99 57 49 33 93
5 30 70 50 90 62 53 51 48 37
43 58 66 46 68 64 55 36 13 59
74 83 17 56 63 34 52 6 54 75
14 27 19 86 60 69 28 92 22 96
4 8 85 61 12 82 73 11 20 42
44 91 81 40 67 29 80 16 24 35Loops structure: {1:8, 2:26, 4:10}
B3-B1: CMS found
0 6 19 3 39 30 1 44 8 16
79 77 12 21 35 76 34 17 99 97
82 88 50 84 24 89 2 81 28 80
5 86 32 72 9 14 57 37 74 4
96 41 43 42 90 45 60 53 48 93
22 33 52 38 63 66 56 36 65 59
85 83 98 54 64 26 55 70 68 91
67 71 51 73 20 69 15 11 94 10
29 27 47 61 23 46 31 87 13 25
7 75 92 49 78 95 40 58 62 18Loops structure: {1:22, 2:24, 3:6, 6:2}
B3-B2: CMS found
0 18 9 10 79 39 25 7 77 2
3 87 84 47 89 15 97 31 1 88
72 38 78 23 98 94 21 71 76 95
41 45 32 26 65 99 57 49 33 93
5 30 70 50 90 62 53 51 48 37
43 58 66 46 68 64 55 36 13 59
74 83 17 56 63 34 52 6 54 75
14 27 19 86 60 69 28 92 22 96
4 8 85 61 12 82 73 11 20 42
44 91 81 40 67 29 80 16 24 35Loops structure: {1:8, 2:26, 4:10}
Видно, что для всех пар лучей Bi-Bj нашлись CMS (случай i=j не рассматривается, тут CMS тривиальна, случаи Bi-Bj и Bj-Bi специально по сути обработаны дважды для перепроверки корректности кода, используемого для поиска CMS).
Пример 2
A = 0123456789123709854640963718259684513072596870243134592806178701635294237596410875128493606840127953
B1 = 5126074389497138506292051487366734952801846971025308134269751640893527738250169425986374103057269148
B2 = 8673054912238019764567512398041029845376789540126305349627819247610538496278315051083764293416528097
B3 = 8673054912239018764567512398041029845376798540126305349627819247610538486279315051083764293416528097B1-B2: -
B1-B3: -
B2-B1: -
B2-B3: CMSs found0 1 2 9 4 5 6 7 8 3
49 95 15 13 14 12 16 17 18 19
20 21 36 23 68 61 26 27 28 29
65 31 84 33 34 35 22 56 38 39
40 71 75 43 44 45 46 76 86 10
97 51 73 87 54 55 37 57 58 59
60 25 62 63 64 30 66 67 24 69
70 41 72 52 99 42 47 77 78 79
80 81 82 83 32 85 48 53 90 89
88 91 92 93 94 11 96 50 98 74Loops structure: {1:62, 2:19}
B3-B1: -
B3-B2: CMS found
0 1 2 9 4 5 6 7 8 3
49 95 15 13 14 12 16 17 18 19
20 21 36 23 68 61 26 27 28 29
65 31 84 33 34 35 22 56 38 39
40 71 75 43 44 45 46 76 86 10
97 51 73 87 54 55 37 57 58 59
60 25 62 63 64 30 66 67 24 69
70 41 72 52 99 42 47 77 78 79
80 81 82 83 32 85 48 53 90 89
88 91 92 93 94 11 96 50 98 74Loops structure: {1:62, 2:19}
В данном примере CMS нашлась только для пары лучей B2 и B3, для других пар CMS не существуют. Схожая ситуация и со звездами с большим числом лучей: для каких-то пар CMS существует, для каких-то — нет. А это, в свою очередь, свидетельствует о том, что в общем случае гипотеза https://vk.com/wall162891802_1177 не верна и не для всех звезд их лучи можно получить путем циклического применения к ним одной и той же CMS. А жаль...
Рассмотрим трешку (структуру типа звезда 1:3) с центральным квадратом A и лучами B1, B2 и B3. Будем искать CMS, попарно отражающие луч Bi в луч Bj с соответствующим отражением центрального квадрата самого в себя. Оказывается, что отражения лучей друг в друга существуют не всегда...
Пример 1
A = 0123456789120467983564903851722578910364895274360198312640573765821490438910752656170329487046598213
B1 = 0428965173869347205112570436989082154736674530128943617985203509817462591023684778346209152176589304
B2 = 0428965173968347205112570436898092154736674530129843617985203509817462591023684778346209152176589304
B3 = 0428765193986347205112570438697082154936694530128743716985203509816472561023974887349206152196587304
B1-B2: CMS found
0 1 2 4 3 5 6 7 8 9
10 11 12 60 14 15 16 17 70 19
20 85 22 23 45 25 26 27 28 29
30 31 32 33 34 35 36 92 38 52
40 41 42 43 44 24 88 47 48 49
50 51 39 53 54 81 71 57 58 59
13 61 62 77 96 65 66 99 68 69
18 56 72 73 74 75 76 63 78 79
80 55 82 83 84 21 86 95 46 89
90 91 37 93 94 87 64 97 98 67
Loops structure: {1:72, 2:14}
B1-B3: CMS found
0 6 19 3 39 30 1 44 8 16
79 77 12 21 35 76 34 17 99 97
82 88 50 84 24 89 2 81 28 80
5 86 32 72 9 14 57 37 74 4
96 41 43 42 90 45 60 53 48 93
22 33 52 38 63 66 56 36 65 59
85 83 98 54 64 26 55 70 68 91
67 71 51 73 20 69 15 11 94 10
29 27 47 61 23 46 31 87 13 25
7 75 92 49 78 95 40 58 62 18
Loops structure: {1:22, 2:24, 3:6, 6:2}
B2-B1: CMS found
0 1 2 4 3 5 6 7 8 9
10 11 12 60 14 15 16 17 70 19
20 85 22 23 45 25 26 27 28 29
30 31 32 33 34 35 36 92 38 52
40 41 42 43 44 24 88 47 48 49
50 51 39 53 54 81 71 57 58 59
13 61 62 77 96 65 66 99 68 69
18 56 72 73 74 75 76 63 78 79
80 55 82 83 84 21 86 95 46 89
90 91 37 93 94 87 64 97 98 67
Loops structure: {1:72, 2:14}
B2-B3: CMS found
0 18 9 10 79 39 25 7 77 2
3 87 84 47 89 15 97 31 1 88
72 38 78 23 98 94 21 71 76 95
41 45 32 26 65 99 57 49 33 93
5 30 70 50 90 62 53 51 48 37
43 58 66 46 68 64 55 36 13 59
74 83 17 56 63 34 52 6 54 75
14 27 19 86 60 69 28 92 22 96
4 8 85 61 12 82 73 11 20 42
44 91 81 40 67 29 80 16 24 35
Loops structure: {1:8, 2:26, 4:10}
B3-B1: CMS found
0 6 19 3 39 30 1 44 8 16
79 77 12 21 35 76 34 17 99 97
82 88 50 84 24 89 2 81 28 80
5 86 32 72 9 14 57 37 74 4
96 41 43 42 90 45 60 53 48 93
22 33 52 38 63 66 56 36 65 59
85 83 98 54 64 26 55 70 68 91
67 71 51 73 20 69 15 11 94 10
29 27 47 61 23 46 31 87 13 25
7 75 92 49 78 95 40 58 62 18
Loops structure: {1:22, 2:24, 3:6, 6:2}
B3-B2: CMS found
0 18 9 10 79 39 25 7 77 2
3 87 84 47 89 15 97 31 1 88
72 38 78 23 98 94 21 71 76 95
41 45 32 26 65 99 57 49 33 93
5 30 70 50 90 62 53 51 48 37
43 58 66 46 68 64 55 36 13 59
74 83 17 56 63 34 52 6 54 75
14 27 19 86 60 69 28 92 22 96
4 8 85 61 12 82 73 11 20 42
44 91 81 40 67 29 80 16 24 35
Loops structure: {1:8, 2:26, 4:10}
Видно, что для всех пар лучей Bi-Bj нашлись CMS (случай i=j не рассматривается, тут CMS тривиальна, случаи Bi-Bj и Bj-Bi специально по сути обработаны дважды для перепроверки корректности кода, используемого для поиска CMS).
Пример 2
A = 0123456789123709854640963718259684513072596870243134592806178701635294237596410875128493606840127953
B1 = 5126074389497138506292051487366734952801846971025308134269751640893527738250169425986374103057269148
B2 = 8673054912238019764567512398041029845376789540126305349627819247610538496278315051083764293416528097
B3 = 8673054912239018764567512398041029845376798540126305349627819247610538486279315051083764293416528097
B1-B2: -
B1-B3: -
B2-B1: -
B2-B3: CMSs found
0 1 2 9 4 5 6 7 8 3
49 95 15 13 14 12 16 17 18 19
20 21 36 23 68 61 26 27 28 29
65 31 84 33 34 35 22 56 38 39
40 71 75 43 44 45 46 76 86 10
97 51 73 87 54 55 37 57 58 59
60 25 62 63 64 30 66 67 24 69
70 41 72 52 99 42 47 77 78 79
80 81 82 83 32 85 48 53 90 89
88 91 92 93 94 11 96 50 98 74
Loops structure: {1:62, 2:19}
B3-B1: -
B3-B2: CMS found
0 1 2 9 4 5 6 7 8 3
49 95 15 13 14 12 16 17 18 19
20 21 36 23 68 61 26 27 28 29
65 31 84 33 34 35 22 56 38 39
40 71 75 43 44 45 46 76 86 10
97 51 73 87 54 55 37 57 58 59
60 25 62 63 64 30 66 67 24 69
70 41 72 52 99 42 47 77 78 79
80 81 82 83 32 85 48 53 90 89
88 91 92 93 94 11 96 50 98 74
Loops structure: {1:62, 2:19}
В данном примере CMS нашлась только для пары лучей B2 и B3, для других пар CMS не существуют. Схожая ситуация и со звездами с большим числом лучей: для каких-то пар CMS существует, для каких-то — нет. А это, в свою очередь, свидетельствует о том, что в общем случае гипотеза https://vk.com/wall162891802_1177 не верна и не для всех звезд их лучи можно получить путем циклического применения к ним одной и той же CMS. А жаль...
Цитата: Yura12 от 02.06.2020, 08:37
А можно ещё спросить вопрос, а вот исследования латинских квадратов, которые идут сейчас, где оно в будущем будет применено?
Пусть не практически, а хотя бы для решения какой-то другой математической проблемы оно будет применено?
А можно ещё спросить вопрос, а вот исследования латинских квадратов, которые идут сейчас, где оно в будущем будет применено?
Пусть не практически, а хотя бы для решения какой-то другой математической проблемы оно будет применено?
Цитата: DimOK от 04.06.2020, 09:42Yura12, "Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях." - Википедия. Также смотрим примечания, где есть ссылки на статьи.
Много научных публикаций по этой теме есть в КиберЛенинке. Еще одно необычное применение - в магии.
Yura12, "Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях." - Википедия. Также смотрим примечания, где есть ссылки на статьи.
Много научных публикаций по этой теме есть в КиберЛенинке. Еще одно необычное применение - в магии.
Цитата: kotenok2000 от 05.06.2020, 06:51в статусе сервера "research progress" был 17 процентов а потом стал 7.
в статусе сервера "research progress" был 17 процентов а потом стал 7.
Цитата: evatutin от 07.06.2020, 11:18Ранее нами была разработана группа простых преобразований (поворот интеркалятов, циклов и нетривиальных латинских подпрямоугольников), позволяющая в некоторых случаях находить новые КФ ОДЛК по имеющимся с малыми затратами вычислительного времени. Эффективное подмножество из них активно используется в проекте в постобработчике найденных КФ ОДЛК (в настоящее время он выполняется на клиенте: если расчет WU'шки на несколько секунд повисает на 100%, значит скорее всего это и есть фаза работы данного постобработчика). Сейчас произведена попытка разработки еще одного простого преобразования, суть которого заключается в попытке замены заданного количества (от 2 до 5) трансверсалей в ДЛК. Версия расчетного модуля в основном подпроекте изменена на 3.2.2, соответствующие WU'шки экспериментов exp725...exp730 добавлены, исследуем эффективность...
PS. Картинка иллюстрирует суть выполняемого простого преобразования: для исходного ДЛК (а) было сброшено 3 трансверсали, в результате чего был получен частично заполненный квадрат (б), из которого затем был получен квадрат (в), отдаваемый на съедение канонизатору, который из ЛК на входе пытается сделать ОДЛК на выходе. Несложно заметить, что квадрат (в) отличается от квадрата (а) поворотом нетривиального латинского подпрямоугольника размером 2х3, т.е. сделанные ранее преобразования поворота интеркалятов и нетривиальных подпрямоугольников являются частными случаями преобразования по замене трансверсалей.
Ранее нами была разработана группа простых преобразований (поворот интеркалятов, циклов и нетривиальных латинских подпрямоугольников), позволяющая в некоторых случаях находить новые КФ ОДЛК по имеющимся с малыми затратами вычислительного времени. Эффективное подмножество из них активно используется в проекте в постобработчике найденных КФ ОДЛК (в настоящее время он выполняется на клиенте: если расчет WU'шки на несколько секунд повисает на 100%, значит скорее всего это и есть фаза работы данного постобработчика). Сейчас произведена попытка разработки еще одного простого преобразования, суть которого заключается в попытке замены заданного количества (от 2 до 5) трансверсалей в ДЛК. Версия расчетного модуля в основном подпроекте изменена на 3.2.2, соответствующие WU'шки экспериментов exp725...exp730 добавлены, исследуем эффективность...
PS. Картинка иллюстрирует суть выполняемого простого преобразования: для исходного ДЛК (а) было сброшено 3 трансверсали, в результате чего был получен частично заполненный квадрат (б), из которого затем был получен квадрат (в), отдаваемый на съедение канонизатору, который из ЛК на входе пытается сделать ОДЛК на выходе. Несложно заметить, что квадрат (в) отличается от квадрата (а) поворотом нетривиального латинского подпрямоугольника размером 2х3, т.е. сделанные ранее преобразования поворота интеркалятов и нетривиальных подпрямоугольников являются частными случаями преобразования по замене трансверсалей.
Цитата: evatutin от 07.06.2020, 11:22Цитата: kotenok2000 от 05.06.2020, 06:51в статусе сервера "research progress" был 17 процентов а потом стал 7.
Я периодически забираю старые WU'шки для анализа результатов и добавляю новые, поэтому на этот % лучше не ориентироваться. В месячных отчетах я публикую % числа исследованных окрестностей обобщенных симметрий (например, см. https://vk.com/wall162891802_1221 — "пройдено 457 (+29) окрестностей из 903 (50,6%, +3,2%)"), он более правильно отражает динамику выполнения данного эксперимента.
Цитата: kotenok2000 от 05.06.2020, 06:51в статусе сервера "research progress" был 17 процентов а потом стал 7.
Я периодически забираю старые WU'шки для анализа результатов и добавляю новые, поэтому на этот % лучше не ориентироваться. В месячных отчетах я публикую % числа исследованных окрестностей обобщенных симметрий (например, см. https://vk.com/wall162891802_1221 — "пройдено 457 (+29) окрестностей из 903 (50,6%, +3,2%)"), он более правильно отражает динамику выполнения данного эксперимента.
Цитата: evatutin от 08.06.2020, 13:20Как уже было неоднократно отмечено ранее, обобщенные симметрии можно описывать перестановками (Px,Py,Pv), задающими соответствие между всеми элементами квадрата
x1 = Px(x2)
y1 = Py(y2)
v1 = Pv(v2)(в простейшем случае, без рассмотрения других парастрофических срезов). Каждая такая группа перестановок описывает соответствующий автоморфизм для квадрата, а если есть автоморфизм, значит (казалось бы) есть причина для снижения мощности соответствующего класса изоморфизма. Однако это не всегда так. Точнее, так будет для всех ЛК, но не для всех ДЛК. Напомню, что класс изоморфизма ДЛК (главный класс), в котором свойства всех квадратов одинаковы, формируется M-преобразованиями, а они в свою очередь могут быть описаны через M-перестановки.
Для примера рассмотрим 3 перестановки:P1 = [9 8 7 6 5 4 3 2 1 0] со структурой мультимножества длин циклов S = {2, 2, 2, 2, 2} = {2:5},
P2 = [0 1 2 3 4 5 6 7 8 9], S = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} = {1:10},
P3 = [0 2 3 1 5 6 4 8 9 7], S = {1, 3, 3, 3} = {1, 3:3}.Перестановки P1 и P2 являются M-перестановками, а P3 — нет. Отсюда можно сделать очень простое наблюдение: если какая-либо обобщенная симметрия описывается комбинацией M-перестановок, то соответствующая мощность главного класса уменьшается, а выбранной комбинации перестановок можно однозначно сопоставить одну из ESODLS схем (будем называть такие обобщенные симметрии M-симметриями). Разумеется, за исключением тривиального случая (P1,P1,P1). Если же хотя бы одна из перестановок не является M-перестановкой, то соответствующей обобщенной симметрии нельзя сопоставить ESODLS схему и уменьшния мощности главного класса не происходит. Например, квадрат
0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
2 0 3 5 8 1 4 6 9 7
4 6 9 7 1 8 2 0 3 5
9 7 8 6 5 4 3 1 2 0
3 4 7 8 0 9 1 2 5 6
6 9 4 1 7 2 8 5 0 3
7 8 5 0 6 3 9 4 1 2
5 3 1 9 2 7 0 8 6 4
8 5 6 2 9 0 7 3 4 1(линия-3, 2 КФ), обладающий горизонтальной симметрией, с позиции обобщенных симметрий описывается перестановками (P2,P1,P1) (или, что то же самое по типам циклов — (1,31,31)), ему соответствует ESODLS схема № 2 со структурой циклов {2:50} и мощность класса изоморфизма 7680 (в 2 раза меньше максимальной).
Квадрат
0 1 2 3 4 5 6 7 8 9
1 2 0 4 8 7 9 5 6 3
7 5 4 2 9 1 8 3 0 6
2 7 8 1 0 3 5 6 9 4
8 6 3 9 5 0 7 4 2 1
9 4 5 8 2 6 1 0 3 7
5 0 9 7 6 4 3 8 1 2
6 3 1 5 7 8 2 9 4 0
3 8 6 0 1 9 4 2 7 5
4 9 7 6 3 2 0 1 5 8(звезда 1:10, 6 КФ) обладает обобщенной симметрией типа (4,31,31), ему соответствует ESODLS схема № 398 со структурой циклов {2:50} и мощность класса изоморфизма 7680 (в 2 раза меньше максимальной).
С другой стороны, квадрат
0 1 2 3 4 5 6 7 8 9
5 9 8 0 2 4 3 6 1 7
8 7 1 4 3 9 2 0 5 6
1 6 9 2 7 8 5 3 4 0
6 0 3 8 5 7 4 2 9 1
4 5 6 7 8 3 1 9 0 2
2 4 5 6 9 0 7 1 3 8
7 3 4 9 1 6 0 8 2 5
9 2 7 5 0 1 8 4 6 3
3 8 0 1 6 2 9 5 7 4(однушка, ESODLS от транспонирования от побочной диагонали) обладает обобщенной симметрией класса (27,27,27) со структурой циклов как в P3, однако ему не соответствует M-симметрий и ESODLS схем (кроме тривиальной), мощность его класса изоморфизма максимальна и равна 15360.
PS. Утверждение "Если квадрат обладает K различными M-симметриями (с соответствующими им нетривиальными ESODLS схемами), то мощность соответствующего ему главного класса = Максимально_возможная_мощность_для_данной_размерности_N / 2^K" неверно. Контрпример:
0 1 2 3 4
2 3 4 0 1
4 0 1 2 3
1 2 3 4 0
3 4 0 1 2Соответствующие ESODLS схемы (кроме тривиальной):
1. Automorphic schema 3
2. Automorphic schema 12
3. Automorphic schema 15
4. Automorphic schema 20
5. Automorphic schema 23
6. Automorphic schema 24
7. Automorphic schema 27Теоретически максимальная мощность главного класса для N=5 — 32.
Мощность главного класса для приведенного квадрата — 4.32 / 2^7 != 4
Что и требовалось доказать.
Как уже было неоднократно отмечено ранее, обобщенные симметрии можно описывать перестановками (Px,Py,Pv), задающими соответствие между всеми элементами квадрата
x1 = Px(x2)
y1 = Py(y2)
v1 = Pv(v2)
(в простейшем случае, без рассмотрения других парастрофических срезов). Каждая такая группа перестановок описывает соответствующий автоморфизм для квадрата, а если есть автоморфизм, значит (казалось бы) есть причина для снижения мощности соответствующего класса изоморфизма. Однако это не всегда так. Точнее, так будет для всех ЛК, но не для всех ДЛК. Напомню, что класс изоморфизма ДЛК (главный класс), в котором свойства всех квадратов одинаковы, формируется M-преобразованиями, а они в свою очередь могут быть описаны через M-перестановки.
Для примера рассмотрим 3 перестановки:
P1 = [9 8 7 6 5 4 3 2 1 0] со структурой мультимножества длин циклов S = {2, 2, 2, 2, 2} = {2:5},
P2 = [0 1 2 3 4 5 6 7 8 9], S = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} = {1:10},
P3 = [0 2 3 1 5 6 4 8 9 7], S = {1, 3, 3, 3} = {1, 3:3}.
Перестановки P1 и P2 являются M-перестановками, а P3 — нет. Отсюда можно сделать очень простое наблюдение: если какая-либо обобщенная симметрия описывается комбинацией M-перестановок, то соответствующая мощность главного класса уменьшается, а выбранной комбинации перестановок можно однозначно сопоставить одну из ESODLS схем (будем называть такие обобщенные симметрии M-симметриями). Разумеется, за исключением тривиального случая (P1,P1,P1). Если же хотя бы одна из перестановок не является M-перестановкой, то соответствующей обобщенной симметрии нельзя сопоставить ESODLS схему и уменьшния мощности главного класса не происходит. Например, квадрат
0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
2 0 3 5 8 1 4 6 9 7
4 6 9 7 1 8 2 0 3 5
9 7 8 6 5 4 3 1 2 0
3 4 7 8 0 9 1 2 5 6
6 9 4 1 7 2 8 5 0 3
7 8 5 0 6 3 9 4 1 2
5 3 1 9 2 7 0 8 6 4
8 5 6 2 9 0 7 3 4 1
(линия-3, 2 КФ), обладающий горизонтальной симметрией, с позиции обобщенных симметрий описывается перестановками (P2,P1,P1) (или, что то же самое по типам циклов — (1,31,31)), ему соответствует ESODLS схема № 2 со структурой циклов {2:50} и мощность класса изоморфизма 7680 (в 2 раза меньше максимальной).
Квадрат
0 1 2 3 4 5 6 7 8 9
1 2 0 4 8 7 9 5 6 3
7 5 4 2 9 1 8 3 0 6
2 7 8 1 0 3 5 6 9 4
8 6 3 9 5 0 7 4 2 1
9 4 5 8 2 6 1 0 3 7
5 0 9 7 6 4 3 8 1 2
6 3 1 5 7 8 2 9 4 0
3 8 6 0 1 9 4 2 7 5
4 9 7 6 3 2 0 1 5 8
(звезда 1:10, 6 КФ) обладает обобщенной симметрией типа (4,31,31), ему соответствует ESODLS схема № 398 со структурой циклов {2:50} и мощность класса изоморфизма 7680 (в 2 раза меньше максимальной).
С другой стороны, квадрат
0 1 2 3 4 5 6 7 8 9
5 9 8 0 2 4 3 6 1 7
8 7 1 4 3 9 2 0 5 6
1 6 9 2 7 8 5 3 4 0
6 0 3 8 5 7 4 2 9 1
4 5 6 7 8 3 1 9 0 2
2 4 5 6 9 0 7 1 3 8
7 3 4 9 1 6 0 8 2 5
9 2 7 5 0 1 8 4 6 3
3 8 0 1 6 2 9 5 7 4
(однушка, ESODLS от транспонирования от побочной диагонали) обладает обобщенной симметрией класса (27,27,27) со структурой циклов как в P3, однако ему не соответствует M-симметрий и ESODLS схем (кроме тривиальной), мощность его класса изоморфизма максимальна и равна 15360.
PS. Утверждение "Если квадрат обладает K различными M-симметриями (с соответствующими им нетривиальными ESODLS схемами), то мощность соответствующего ему главного класса = Максимально_возможная_мощность_для_данной_размерности_N / 2^K" неверно. Контрпример:
0 1 2 3 4
2 3 4 0 1
4 0 1 2 3
1 2 3 4 0
3 4 0 1 2
Соответствующие ESODLS схемы (кроме тривиальной):
1. Automorphic schema 3
2. Automorphic schema 12
3. Automorphic schema 15
4. Automorphic schema 20
5. Automorphic schema 23
6. Automorphic schema 24
7. Automorphic schema 27
Теоретически максимальная мощность главного класса для N=5 — 32.
Мощность главного класса для приведенного квадрата — 4.
32 / 2^7 != 4
Что и требовалось доказать.