Математический форум Math Help Planet
http://mathhelpplanet.com/

Ортогональные латинские квадраты 10-го порядка
http://mathhelpplanet.com/viewtopic.php?f=57&t=46638
Страница 2 из 421

Автор:  Nataly-Mak [ 18 янв 2016, 09:39 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Avgust писал(а):
Но разве трудно перелолпатить все-все варианты для n=10 ?

Наверное, трудно, потому что вариантов мириады.
Смотрите: 10 элементов в первой строке, вариантов заполнения только первой строки 10!.
А дальше: вторую строку тоже можно заполнить 10! способами (правда, с некоторым минусом уже - так как конкретное заполнение первой строки уже отсекает некоторые варианты заполнения второй строки), и третью - тоже, и т. д.
Это в одном квадрате. А потом надо к нему подстроить второй квадрат, чтобы пара получилась ортогональная, а потом ещё и третий квадрат найти, чтобы он был ортогонален первым двум.
Если б всё было так просто, давно бы перелопатили.

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

Кстати, и для групп MOLS других порядков изобрели немало разных алгоритмов. Вот только для порядка 10 ничего хорошего не изобрели пока. А перебором в лоб тут ничего не сделаешь.

Автор:  Nataly-Mak [ 19 янв 2016, 05:59 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Нашла статью в Интернете
https://cs.anu.edu.au/~./bdm/papers/ls_final.pdf

Цитирую:

Цитата:
Meanwhile, no set of 3 MOLS of order 10 has yet been found, despite a considerable
amount of effort by many people. See [1, 9, 11, 12, 13, 14, 15, 36, 37, 41, 42, 54] for
some representative partial results. In this paper we will add our own contribution to this
quest; namely, we will describe computations that show that none of the 8,500,842,802
main classes of Latin squares with non-trivial autoparatopy groups lie in a set of 3 MOLS
(where the other two squares may have trivial groups). We believe this to be by far the
largest systematic search so far undertaken for 3 MOLS of order 10.

И далее цитирую часть списка литературы - как раз те работы, в которых пытались найти тройку попарно ортогональных ЛК 10-го порядка:

Цитата:
[9] A. E. Brouwer, Four MOLS of order 10 with a hole of order 2, J. Statist. Plann.
Inference, 10 (1984) 203–205.
[11] J. W. Brown, An extension of Mann’s theorem to a triple of mutually orthogonal
Latin squares of order 10. J. Combin. Theory Ser. A, 12 (1972) 316–318.
[12] J. W. Brown and E. T. Parker, A try for three order-10 orthogonal Latin squares,
Congr. Numer., 36 (1982) 143–144.
[13] J. W. Brown and E. T. Parker, Some attempts to construct orthogonal Latin squares,
Congr. Numer., 43 (1984) 201–202.
[14] J. W. Brown and E. T. Parker, An attempt to construct three mols ◦10 with a common
transversal, Algebras Groups Geom., 2 (1985) 258–262.
[15] J. W. Brown and E. T. Parker, More on order 10 turn-squares, Ars Combin., 35
(1993) 125–127.

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

Автор:  Nataly-Mak [ 19 янв 2016, 06:16 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Теперь показываю обещанный алгоритм построения пар ОЛК 10-го порядка, основанный на квази-разностной матрице.
Сразу иллюстрация

Изображение

Сверху на иллюстрации вы видите квази-разностную матрицу, далее для краткости будет использоваться аббревиатура КРМ.
Первые две строки КРМ - это координаты; около ЛК координаты - сиреневые строка и столбец, они к ЛК не принадлежат.
Символьный элемент [math]a=9[/math].
Окрашенные в жёлтый цвет ячейки - это то, что заполняется по значениям, соответствующим координатам. Далее заполнение идёт по диагоналям ЛК циклическим сдвигом набора (0, 1, 2, 3, 4, 5, 6, 7, 8).
Первому ЛК соответствует третья строка КРМ, второму ЛК - четвёртая строка КРМ.

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

Если тут всё понятно и вопросов нет, продолжу чуть позже.

Автор:  Nataly-Mak [ 19 янв 2016, 08:03 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Цитата:
Ну, и разумеется, все элементы в каждой строке должны быть различные.

Тут не совсем точно выразилась: элементов в каждой строке КРМ 11, различными должны быть 10 элементов из 11.
Ну, естественно, первая строка не в счёт, в ней вообще одни нули и символьный элемент a.

Автор:  Nataly-Mak [ 19 янв 2016, 08:41 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

А теперь отчёт форумчанина tolstopuz на форуме dxdy.ru об эксперименте:
Цитата:
Итак, найдено:
- 2025 трехстрочных КРМ;
- 3240 четырехстрочных КРМ;
- 0 пятистрочных КРМ.

Естественно, четырехстрочные КРМ попарно связаны перестановкой третьей и четвертой строк, так что интересных из них только 1620.

http://dxdy.ru/post202837.html#p202837

Как видно из отчёта, tolstopuz начинал с поиска трёхстрочных КРM, это значит: к двум координатным строкам КРМ добавляется третья строка, удовлетворяющая критерию совместимости. Это будет соответствовать только одному ЛК, построенному данным способом.
Таких ЛК судя по отчёту найдено 2025 штук. Богато :)
Далее для каждого варианта трёхстрочной КРМ ищется четвёртая строка, если она найдена, это уже получена пара ОЛК. Как видим, пар ОЛК тоже найдено немало - 1620 различных.

А теперь внимание! Самое интересное в эксперименте - попыка добавить в КРМ пятую строку. Это и есть попытка найти тройку попарно ортогональных ЛК. Увы, попытка не увенчалась успехом.
Но можно попытаться по этому алгоритму искать псевдотройки.

К этой КРМ
a 0 0 0 0 0 0 0 0 0 0 
0 a 0 1 2 3 4 5 6 7 8
1 1 a 5 8 3 2 7 0 6 4
1 2 5 a 6 0 4 3 8 1 7

в эксперименте был найден такой вариант четвёртой строки:
0 8 3 6 1 0 5 7 4 2 a

Сейчас попробую по этой строке построить второй ЛК ортогональный первому (первый ЛК остаётся такой же, как показано выше, потому что третья строка КРМ не изменилась).

Автор:  Nataly-Mak [ 19 янв 2016, 09:15 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

КРМ будет такая:

a 0 0 0 0 0 0 0 0 0 0 
0 a 0 1 2 3 4 5 6 7 8
1 1 a 5 8 3 2 7 0 6 4
0 8 3 6 1 0 5 7 4 2 a

Второй ЛК, соответствующий четвёртой строке КРМ:

3 9 4 7 2 1 6 8 5 0
6 4 9 5 8 3 2 7 0 1
1 7 5 9 6 0 4 3 8 2
0 2 8 6 9 7 1 5 4 3
5 1 3 0 7 9 8 2 6 4
7 6 2 4 1 8 9 0 3 5
4 8 7 3 5 2 0 9 1 6
2 5 0 8 4 6 3 1 9 7
9 3 6 1 0 5 7 4 2 8
8 0 1 2 3 4 5 6 7 9

Всё правильно: этот ЛК ортогонален ЛК, соответствующему третьей строке КРМ (показан выше).

Если кто-нибудь вник в алгоритм, пожалуйста, попробуйте добавление пятой строки к КРМ.
Только надо ослабить критерий совместимости строк, чтобы получить псевдотройки.
То есть надо потребовать ортогональность 1-го и 2-го ЛК, 1-го и 3-го ЛК, а вот 2-ой с 3-им могут быть не ортогональными (третьему ЛК будет соответствовать пятая строка КРМ).

А я сейчас поищу в своих статьях КРМ другого типа.
Кстати, вот мои статьи, посвящённые КРМ:
http://www.natalimak1.narod.ru/quazi.htm
http://www.natalimak1.narod.ru/quazi1.htm
http://www.natalimak1.narod.ru/quazi2.htm

Автор:  Avgust [ 19 янв 2016, 09:26 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Nataly-Mak
Вы так убежали вперед паровоза, что даже в бинокль не угнаться за мыслями :good:

Автор:  Nataly-Mak [ 19 янв 2016, 09:31 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Avgust
пожалуйста, ваши вопросы.
Я остановлюсь и попробую разъяснить непонятные места.
Мне-то кажется всё простым и очевидным, потому что занималась этим раньше.

Автор:  Nataly-Mak [ 19 янв 2016, 10:05 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Кстати, псевдотройка к нас вроде как уже и получилась: перый ЛК, соответствующий третьей строке КРМ, второй ЛК - соответствующий четвёртой строке КРМ в её первом варианте; эти два ЛК показаны на иллюстрации, они ортогональны.

Теперь построили ещё один ЛК по новой чётвёртой строке КРМ, этот ЛК тоже ортогонален первому ЛК. А вот второму ЛК (см. на иллюстрации) он не ортогонален.

Осталось посмотреть, много ли ошибок в не ортогональной паре ЛК.

Автор:  Nataly-Mak [ 19 янв 2016, 10:24 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Показываю три ЛК полученной псевдотройки:

№1
9 5 8 3 2 7 0 6 4 1
5 9 6 0 4 3 8 1 7 2
8 6 9 7 1 5 4 0 2 3
3 0 7 9 8 2 6 5 1 4
2 4 1 8 9 0 3 7 6 5
7 3 5 2 0 9 1 4 8 6
0 8 4 6 3 1 9 2 5 7
6 1 0 5 7 4 2 9 3 8
4 7 2 1 6 8 5 3 9 0
1 2 3 4 5 6 7 8 0 9

№2
5 8 3 2 7 0 6 4 9 1
9 6 0 4 3 8 1 7 5 2
6 9 7 1 5 4 0 2 8 3
0 7 9 8 2 6 5 1 3 4
4 1 8 9 0 3 7 6 2 5
3 5 2 0 9 1 4 8 7 6
8 4 6 3 1 9 2 5 0 7
1 0 5 7 4 2 9 3 6 8
7 2 1 6 8 5 3 9 4 0
2 3 4 5 6 7 8 0 1 9

№3
3 9 4 7 2 1 6 8 5 0
6 4 9 5 8 3 2 7 0 1
1 7 5 9 6 0 4 3 8 2
0 2 8 6 9 7 1 5 4 3
5 1 3 0 7 9 8 2 6 4
7 6 2 4 1 8 9 0 3 5
4 8 7 3 5 2 0 9 1 6
2 5 0 8 4 6 3 1 9 7
9 3 6 1 0 5 7 4 2 8
8 0 1 2 3 4 5 6 7 9

Это квадрат, составленный из пар соотвествующих элементов не ортогональных ЛК №2 и №3:
53  89  34  27  72  01  66  48  95  10 
96 64 09 45 38 83 12 77 50 21
61 97 75 19 56 40 04 23 88 32
00 72 98 86 29 67 51 15 34 43
45 11 83 90 07 39 78 62 26 54
37 56 22 04 91 18 49 80 73 65
84 48 67 33 15 92 20 59 01 76
12 05 50 78 44 26 93 31 69 87
79 23 16 61 80 55 37 94 42 08
28 30 41 52 63 74 85 06 17 99

Много ошибок?
У меня в программе нет подсчёта повторений, надо добавить, чтобы искала повторения.

Страница 2 из 421 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/