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

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

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

Визуально отметила все повторения:

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

У меня получилась отличная псевдотройка!!
В проекте SAT первая найденная псевдотройка имела ортогональность всего в 70 ячейках из 100 (и, как я поняла, лучших решений пока не найдено).
А в моей псевдотройке ортогональность есть в 82 ячейках из 100 (18 не уникальных элементов, каждый из которых повторен один раз).
Конечно, у иностранцев результат лучше - у них ортогональность в 91 ячейке из 100.

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

Там у tolstopuz показан ещё один вариант четвёртой строки - для другой КРМ.
Сейчас сочиню по этому варианту ещё одну псевдотройку.

Вот для этой КРМ

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 7 5 2 4 0 8 3 6
2 1 7 5 2 4 0 8 3 6 a

tolstopuz нашёл такой вариант четвёртой строки:

0 1 6 a 7 5 2 4 0 8 3

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

Псевдотройка #2

ЛК №1

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

ЛК №2

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

ЛК №3

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

ЛК №1 и №2 ортогональны, ЛК №1 и №3 ортогональны, ЛК №2 и №3 не ортогональны.
Это проверочный квадрат:

76 94 81* 63 38* 57* 12 05* 49 20
59 87 95 02* 74 40* 68* 23 16* 31
27* 69 08 96 13* 85 51* 70* 34 42
45 38* 79 10 97 24* 06 62* 81* 53
02* 56 40* 89 21 98 35* 17 73* 64
84* 13* 67 51* 09 32 90 46* 28 75
30 05* 24* 78 62* 19 43 91 57* 86
68* 41 16* 35* 80 73* 29 54 92 07
93 70* 52 27* 46* 01 84* 39 65 18
11 22 33 44 55 66 77 88 00 99

К сожалению, получился точно такой же результат: ортогональность нарушена в 18 ячейках из 100.

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

Итак, показываю КРМ другого типа.
Показанные выше ОЛК содержали подквадрат 1х1. Теперь ЛК будут содержать подквадрат 3х3 (вы видите этот подквадрат выделенным на иллюстрации - в правом нижнем углу каждого ЛК).
В КРМ для такого типа ЛК критерий совместимости строк такой: все разности соответствующих элементов в любых двух строках КРМ должны быть различны по модулю 7 (n-3, n - порядок ЛК, 3 - порядок подквадрата). При этом также разности, содержащие символьные элементы, не считаются.

Изображение

На иллюстрации изображена знаменитая пара ОЛК Паркера
см. статью http://www.natalimak1.narod.ru/quazi1.htm

Символьные элементы a, b, c принимают значения 7, 8, 9 в любой комбинации. Пример с конкретными значениями символьных элементов смотрите в указанной статье.

Чтобы получить псевдотройку, надо найти другой вариант четвёртой строки в приведённой КРМ, как это было сделано в эксперименте tolstopuz, если такой вариант существует.
Можно попытаться добавлять и пятую строку в КРМ, ослабив критерий совместимости строк - для получения псевдотройки.
Если бы пятую строку удалось добавить с полным выполнением критерия совместимости строк - это означало бы решение задачи о поиске тройки попарно ортогональных ЛК 10-го порядка.

Кто может выполнить эксперимент с этой знаменитой КРМ Паркера?
Может быть, найдётся псевдотройка лучше, чем у иностранцев.
Ну, о совсем правильной тройке можно только мечтать...

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

Второй вариант КРМ для ОЛК с подквадратом 3х3

Изображение

Автор этой ортогональной пары ЛК Stinson.
Все условия точно такие же, как для предыдущей пары - Паркера.
По идее, если начать с двух первых строк КРМ (координатных), то оба эти варианта должны найтись, если реализовать программный поиск.

И ещё далее покажу третий вариант. Две координатные строки в КРМ точно такие же, как в показанных двух вариантах, а третья и четвёртая строки другие, что даёт новую пару ОЛК.

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

И вот третий вариант (пара найдена в Интернете)

Изображение

Итак, ещё раз: обратим внимание на КРМ этих трёх вариантов.
1. первые две строки (координатные) одинаковы во всех трёх вариантах;
2. третья и четвёртая строки соответствуют первому и второму ортогональным ЛК.
Бросается в глаза, что символьные элементы в третьей и четвёртой строках этих трёх вариантов КРМ расположены по-разному.

Осталось выполнить эксперимент.
Начинаем поиск с третьей строки КРМ, задав первые две (координатные строки), как они заданы в приведённых КРМ.
Найдя третью строку КРМ, мы найдёи первый ЛК искомой пары ортогональных квадратов. Затем для найденной третьей строки ищем четвёртую строку, которая даст второй ЛК, ортогональный первому. Если удастся найти несколько вариантов четвёртой строки для конкретной третьей строки, - это уже будут псевдотройки.
Тут всё ещё неизведано - что и как оно получится.
У нас есть пока только один эксперимент, но он для КРМ другого типа - для ЛК с подквадратом 1х1.

Замечание: эта пара ОЛК записана в нетрадиционном виде - все элементы ЛК увеличены на 1. Можно привести и ЛК, и КРМ к традиционной записи, уменьшив все элементы на 1.

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

Вернусь к КРМ для пар ОЛК, в которых ЛК содержат подквадрат 1х1.
Выше были представлены такие КРМ.
У меня в статье написано, что одним из исходных квадратов был взят ЛК Лямзина.
В статье вы видите этот ЛК на рис. 23. Это первый ЛК пары ОЛК Лямзина.
Мне тогда очень понравилась идеальная симметрия этого ЛК и я попробовала найти другой вариант такого квадрата. Написала программу, выполнила, квадрат такой нашёлся (в статье он изображён на рис. 24). Далее, выполнив программу перестановки строк в этом ЛК, я нашла и ортогональный ему ЛК.
Но теперь покажу преобразованный квадрат с рис. 24.
Преобразования очень простые:
1. переместила крайний левый столбец вправо - последним;
2. переместила верхнюю строку вниз;
3. сделала взимозамену элементов: 0 -> 9, 9 -> 0.
Вот и все преобразования. Эти преобразования мне понадобились, чтобы применить к ЛК квази-разностную матрицу.
Результат смотрите на иллюстрации. Вы видите КРМ, соответствующую первому ЛК ортогональной пары и сам этот ЛК.

Изображение

(Верхняя строка и левый столбец координатные, они не относятся к ЛК; я оставила их для наглядности.)
Диагональная симметрия в этом ЛК идеальная, как и в найденном в Сети оригинальном ЛК Лямзина.

Avgust
вам это должно очень понравиться :)

Далее покажу, как я пристроила к этому ЛК ортогональный ему ЛК; этому ортогональному ЛК соответствует четвёртая строка КРМ.
Подчеркну, что этот ортогональный ЛК я нашла не работая с КРМ, а просто перестановкой строк в первом ЛК.
(Почему я решила искать ортогональный ЛК перестановкой строк в первом ЛК? Потому что так в оригинальной паре ОЛК Лямзина: второй ЛК получается из первого перестановкой строк.)

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

Продолжаю. Теперь вы видите на иллюстрации КРМ для пары ОЛК и сами эти ортогональные ЛК.

Изображение

Симметрия во втором ЛК уже не такая идеальная, как в первом ЛК, произошло небольшое смещение. Это и понятно: второй ЛК получен из первого перестановкой строк.
Итак, пара ОЛК, аналогичная оригинальной паре ОЛК Лямзина, была найдена.
Далее я выложила эту КРМ на форуме dxdy.ru, где форумчанин tolstopuz выполнил эксперимент с этой КРМ.
И он выложил вариант четвёртой строки этой КРМ! Это дало ещё одну пару ОЛК. В результате образовалась... псевдотройка! Но мы в то время не искали псевдотройки, мы хотели найти хорошую тройку - не ложную. Увы, это у нас не получилось.

Напомню, это всё мы проделали в 2009 году. Найденная нами псевдотройка оказалась намного лучше псевдотройки, найденной в проекте SAT в 2012-2013 гг. У них ортогональность в не ортогональной паре была всего в 70 ячейках из 100, а в нашей псевдотройке - в 82 ячейках из 100.
Но недавно иностранцы нашли ещё лучшее приближение к решению - у них ортогональность есть в 91 ячейках из 100.

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

Nataly-Mak
Да! Чертовски захватывающая по всем диагоналям. Наверное, идеальное решение близко от ваших.

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

Показываю нашу псевдотройку

Изображение

(В ЛК №3 не закрашена одна ячейка - в нижнем правом углу, должна быть салатного цвета.)

ЛК №1 и №2 ортогональны, ЛК №1 и №3 ортогональны, ЛК №2 и №3 не ортогональны; ортогональность нарушена в 18 ячейках из 100.
Проверочный квадрат для не ортогональной пары ЛК был показан выше. Продублирую его здесь для большей наглядности:

76 94 81* 63 38* 57* 12 05* 49 20
59 87 95 02* 74 40* 68* 23 16* 31
27* 69 08 96 13* 85 51* 70* 34 42
45 38* 79 10 97 24* 06 62* 81* 53
02* 56 40* 89 21 98 35* 17 73* 64
84* 13* 67 51* 09 32 90 46* 28 75
30 05* 24* 78 62* 19 43 91 57* 86
68* 41 16* 35* 80 73* 29 54 92 07
93 70* 52 27* 46* 01 84* 39 65 18
11 22 33 44 55 66 77 88 00 99

Звёздочкой помечены не уникальные элементы, их 18 штук, каждый повторен.

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