Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 2 из 421 |
[ Сообщений: 4210 ] | На страницу Пред. 1, 2, 3, 4, 5 ... 421 След. |
|
Автор | Сообщение | |
---|---|---|
Nataly-Mak |
|
|
Avgust писал(а): Но разве трудно перелолпатить все-все варианты для n=10 ? Наверное, трудно, потому что вариантов мириады. Смотрите: 10 элементов в первой строке, вариантов заполнения только первой строки 10!. А дальше: вторую строку тоже можно заполнить 10! способами (правда, с некоторым минусом уже - так как конкретное заполнение первой строки уже отсекает некоторые варианты заполнения второй строки), и третью - тоже, и т. д. Это в одном квадрате. А потом надо к нему подстроить второй квадрат, чтобы пара получилась ортогональная, а потом ещё и третий квадрат найти, чтобы он был ортогонален первым двум. Если б всё было так просто, давно бы перелопатили. Для построения пар ОЛК 10-го порядка придумали несколько очень красивых алгоритмов. Об одном из них, связанным с квази-разностной матрицей, я расскажу далее. Кстати, и для групп MOLS других порядков изобрели немало разных алгоритмов. Вот только для порядка 10 ничего хорошего не изобрели пока. А перебором в лоб тут ничего не сделаешь. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Нашла статью в Интернете
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 |
|
|
Теперь показываю обещанный алгоритм построения пар ОЛК 10-го порядка, основанный на квази-разностной матрице.
Сразу иллюстрация Сверху на иллюстрации вы видите квази-разностную матрицу, далее для краткости будет использоваться аббревиатура КРМ. Первые две строки КРМ - это координаты; около ЛК координаты - сиреневые строка и столбец, они к ЛК не принадлежат. Символьный элемент [math]a=9[/math]. Окрашенные в жёлтый цвет ячейки - это то, что заполняется по значениям, соответствующим координатам. Далее заполнение идёт по диагоналям ЛК циклическим сдвигом набора (0, 1, 2, 3, 4, 5, 6, 7, 8). Первому ЛК соответствует третья строка КРМ, второму ЛК - четвёртая строка КРМ. Здесь показана пара ОЛК, построенная по данной КРМ. Строки КРМ должны удовлетворять критерию совместимости: разности между соответствующими элементыми любых двух строк должны быть различными по модулю 9. При этом разности, содержащие символьный элемент, не считаются. В этом и только в этом случае два ЛК, построенные по КРМ, будут ортогональными. Ну, и разумеется, все элементы в каждой строке должны быть различные. Если тут всё понятно и вопросов нет, продолжу чуть позже. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Цитата: Ну, и разумеется, все элементы в каждой строке должны быть различные. Тут не совсем точно выразилась: элементов в каждой строке КРМ 11, различными должны быть 10 элементов из 11. Ну, естественно, первая строка не в счёт, в ней вообще одни нули и символьный элемент a. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
А теперь отчёт форумчанина 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 8 3 6 1 0 5 7 4 2 a Сейчас попробую по этой строке построить второй ЛК ортогональный первому (первый ЛК остаётся такой же, как показано выше, потому что третья строка КРМ не изменилась). |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
КРМ будет такая:
a 0 0 0 0 0 0 0 0 0 0 Второй ЛК, соответствующий четвёртой строке КРМ: 3 9 4 7 2 1 6 8 5 0 Всё правильно: этот ЛК ортогонален ЛК, соответствующему третьей строке КРМ (показан выше). Если кто-нибудь вник в алгоритм, пожалуйста, попробуйте добавление пятой строки к КРМ. Только надо ослабить критерий совместимости строк, чтобы получить псевдотройки. То есть надо потребовать ортогональность 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 Последний раз редактировалось Nataly-Mak 19 янв 2016, 09:48, всего редактировалось 2 раз(а). |
||
Вернуться к началу | ||
За это сообщение пользователю Nataly-Mak "Спасибо" сказали: Avgust |
||
Avgust |
|
|
Nataly-Mak
Вы так убежали вперед паровоза, что даже в бинокль не угнаться за мыслями |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Avgust
пожалуйста, ваши вопросы. Я остановлюсь и попробую разъяснить непонятные места. Мне-то кажется всё простым и очевидным, потому что занималась этим раньше. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Кстати, псевдотройка к нас вроде как уже и получилась: перый ЛК, соответствующий третьей строке КРМ, второй ЛК - соответствующий четвёртой строке КРМ в её первом варианте; эти два ЛК показаны на иллюстрации, они ортогональны.
Теперь построили ещё один ЛК по новой чётвёртой строке КРМ, этот ЛК тоже ортогонален первому ЛК. А вот второму ЛК (см. на иллюстрации) он не ортогонален. Осталось посмотреть, много ли ошибок в не ортогональной паре ЛК. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Показываю три ЛК полученной псевдотройки:
№1 9 5 8 3 2 7 0 6 4 1 №2 5 8 3 2 7 0 6 4 9 1 №3 3 9 4 7 2 1 6 8 5 0 Это квадрат, составленный из пар соотвествующих элементов не ортогональных ЛК №2 и №3: 53 89 34 27 72 01 66 48 95 10 Много ошибок? У меня в программе нет подсчёта повторений, надо добавить, чтобы искала повторения. |
||
Вернуться к началу | ||
На страницу Пред. 1, 2, 3, 4, 5 ... 421 След. | [ Сообщений: 4210 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
О теме "Отрогональные латинские квадраты 10-го порядка" | 21 |
2543 |
14 июн 2018, 05:28 |
|
Ортогональные пространства
в форуме Функциональный анализ, Топология и Дифференциальная геометрия |
0 |
330 |
18 ноя 2014, 18:53 |
|
Ортогональные векторы
в форуме Векторный анализ и Теория поля |
2 |
236 |
02 ноя 2021, 15:04 |
|
Ортогональные собственные вектора | 0 |
225 |
18 апр 2019, 23:18 |
|
Ортогональные центральные композиционный план | 2 |
463 |
08 дек 2016, 09:20 |
|
Ряд Фурье и другие ортогональные разложения | 1 |
486 |
29 апр 2015, 14:47 |
|
Обобщенные вещественно ортогональные формы в радиосвязи
в форуме Линейная и Абстрактная алгебра |
2 |
557 |
14 июн 2015, 13:37 |
|
Квадраты | 20 |
743 |
18 июл 2021, 17:46 |
|
Доказать, что ортогональные проекции вершин н-мерного куба
в форуме Геометрия |
13 |
461 |
18 сен 2020, 21:29 |
|
Квадраты в окружности
в форуме Начала анализа и Другие разделы школьной математики |
8 |
562 |
20 май 2020, 09:48 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 20 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |