Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 421 |
[ Сообщений: 4210 ] | На страницу 1, 2, 3, 4, 5 ... 421 След. |
|
Автор | Сообщение | |
---|---|---|
Nataly-Mak |
|
|
В дальнейшем вместо "латинский квадрат" для краткости будем использовать аббревиатуру ЛК. Сразу замечу, что здесь будут рассматриваться классические ЛК 10-го порядка. Есть ещё обобщённые ЛК, которые здесь не рассматриваются. Пример ЛК 10-го порядка 0 4 1 7 2 9 8 3 6 5 Определение 1 ЛК называется диагональным, если в каждой из двух главных диагоналей все элементы различные. В приведённом выше примере это свойство выполняется только в одной главной диагонали. Пример диагонального ЛК 10-го порядка 0 9 4 6 1 7 5 8 2 3 Определение 2 два ЛК называются ортогональными, если все пары, составленные из элементов соответствующих ячеек ЛК, различны. Пример пары ортогональных ЛК 10-го порядка квадрат №1 0 4 1 7 2 9 8 3 6 5 квадрат №2 0 7 8 6 9 3 5 4 1 2 Это знаменитая пара Паркера. (см. статью "Ортогональные латинские квадраты 10-го порядка") Квадрат, составленный из пар чисел, образованных элементами двух данных ЛК: 00 47 18 76 29 93 85 34 61 52 Этот квадрат называют греко-латинским квадратом или квадратом Эйлера. Интересно, что для порядка 10 греко-латинский квадрат - уже готовый магический квадрат. Разве что для более привычного традициооного вида магического квадрата можно увеличить все элементы на единицу. Почему тема именно об ортогональных ЛК 10-го порядка? Это задача не только века, а уже двух веков. Поиск тройки попарно ортгональных ЛК 10-го порядка вели в прошлом веке и продолжают вести в веке нынешнем. До сих пор такая тройка не найдена. Далее расскажу о российском проекте распределённых вычислений по поиску ортогональных ЛК 10-го порядка. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Просматривая недавно Гостевую книгу своего сайта, наткнулась на сообщение от 1.11.2012 г.
Цитата: Здравствуйте. Я научный сотрудник ИДСТУ СО РАН, программист проекта SAT@home. Мы сейчас ищем пары ОДЛК порядка 10, один уже нашли http://sat.isa.ru/pdsat/solutions.php. У Вас в статье нашел упоминание, что известны 3 пары ОДЛК порядка 10. Подскажите пожалуйста, какие именно пары известны и откуда эта информация. И насколько будет значимо если найдутся ранее неизвестные пары ОДЛК порядка 10? Это написал один из организаторов проекта распределённых вычислений Олег Заикин. Ссылка на статью, которую упоминает Олег, приведена выше. Цитирую эту статью: Цитата: Итак, в 1958-1959 гг. было составлено много пар ОЛК 10-го порядка. А пары диагональных ОЛК 10-го порядка были найдены только в 1992 г. Эти пары опубликованы в статье “Completion of the Spectrum of Orthogonal Diagonal Latin Squares” (J. W. Brown и другие). Покажу первую пару ортогональных диагональных ЛК 10-го порядка: №1 0 9 4 6 1 7 5 8 2 3 №2 0 8 5 1 7 3 4 6 9 2 Ещё две пары смотрите в указанной статье. Итак, одной из задач, решаемых в проекте, является задача поиска пар ортогональных диагональных ЛК 10-го порядка (сокращённо - ОДЛК). По ссылке http://sat.isa.ru/pdsat/solutions.php вы можете посмотреть результаты поиска. Самая последняя пара ОДЛК была найдена 13.01.2016 г. Вот она: №1 0 1 2 3 4 5 6 7 8 9 №2 0 1 2 3 4 5 6 7 8 9 |
||
Вернуться к началу | ||
laperino |
|
|
Nataly-Mak писал(а): Поиск тройки попарно ортгональных ЛК 10-го порядка вели в прошлом веке и продолжают вести в веке нынешнем. До сих пор такая тройка не найдена. По памяти, в 2004-2007 годах откуда-то в инете взял тройку попарно орт. лат. квадратов то ли 10 -го порядка, то ли 12-го и по своей методе искал в ней выход на 4-ый квадрат, но увы. Однако, записи не выбросил и точно они сохранились. Не могу покамест себя заставить переворушить горы, десятки кг. черновиков. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
laperino писал(а): По памяти, в 2004-2007 годах откуда-то в инете взял тройку попарно орт. лат. квадратов то ли 10 -го порядка, то ли 12-го и по своей методе искал в ней выход на 4-ый квадрат, но увы. Однако, записи не выбросил и точно они сохранились. Это не могла быть тройка MOLS (попарно ортогональных ЛК) 10-го порядка. Есть свежая статья, ссылку на которую мне прислал на днях Олег Заикин; в этой статье сообщается о найденной группой иностранцев псевдотройке с нарушенной ортогональностью в 9 ячейках одной из трёх пар ЛК. Об этой статье напишу далее. У меня тоже есть алгоритм поиска тройки MOLS 10-го порядка, основанный на квази-разностных матрицах. Опишу его подробно позже. На форуме dxdy.ru в теме "Магические квадраты" подробно изложен этот алгоритм. Один форумчанин реализовал этот алгоритм программно и выполнил один эксперимент. Он выложил в теме подробный отчёт об эксперименте. Забегая вперёд: отчёт выложен тут http://dxdy.ru/post202837.html#p202837 алгоритм - тут http://dxdy.ru/post202706.html#p202706 (это 2009 год) |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Нашла в Интернете ссылку на статью "Поиск систем ортогональных латинских квадратов в проекте добровольных вычислений SAN@home" (авторы: Заикин О. С., Кочемазов С. Е., А. А. Семенов)
http://www.docme.ru/doc/846801/ortogona ... e-kvadraty Цитирую эту статью: Цитата: Тройка попарно ортогональных латинских квадратов В каждом квадрате была зафиксирована первая строка (значение «0 1 2 3 4 5 6 7 8 9»). Декомпозиция проводилась по второй строке первого квадрата – перебирались все возможные варианты ее заполнения (всего 1334961 вариантов, каждому варианту соответствует подзадача). Эксперимент по решению данной задачи в SAT@home был запущен 24 июня 2013 года и продолжался примерно месяц. В результате нашлась такая тройка A, B, C, что A ортогонален B, A ортогонален C, а квадраты B и C ортогональны в 70 ячейках из 100. После этого был запущен поиск тройки квадратов, в которой на B и C было наложено условие «ортогональны минимум в 71 ячейке из 100». КНФ, кодирующая данную задачу, состоит из 36685 переменных и 1625560 дизъюнктов, файл с КНФ занимает 23 мегабайта. Эта задача решается в проекте в настоящий момент. По 5 ячеек во 2-ой и 3-ей строках. Мировой рекорд – 91 ячейка из 100 (Wanless). Цель – получить новый рекорд. Два дня назд Олег прислал мне ссылку на статью, содержащую рекордную псевдотройку. Далее я покажу эту псевдотройку. Псевдотройки, найденные в проекте, вы можете посмотреть по приведённой в стартовом сообщении ссылке. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Nataly-Mak писал(а): Интересно, что для порядка 10 греко-латинский квадрат - уже готовый магический квадрат. Разве что для более привычного традициооного вида магического квадрата можно увеличить все элементы на единицу. Уточнение: конечно, магический квадрат получится из греко-латинского квадрата, составленного из элементов пары ортогональных диагональных ЛК. Если же ЛК не диагональные, то получится полумагический квадрат (не будет нужной суммы чисел в одной или в обеих главных диагоналях квадрата). Очень редко бывают случаи, когда ортогональные ЛК не диагональные, но магический квадрат дают; это тогда, когда сумма элементов в обеих главных диагоналях ЛК равна сумме элементов в строках и столбцах ЛК. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Итак, ссылка на статью, содержащую недавно найденную рекордную псевдотройку
http://www.ams.org/journals/mcom/2016-8 ... 3010-5.pdf Показываю эту псевдотройку: квадрат А 0 8 9 7 5 6 4 2 3 1 квадрат В 0 7 8 9 1 2 3 4 5 6 квадрат С 0 7 8 9 1 2 3 4 5 6 Квадраты А и В ортогональны, квадраты А и С ортогональны, а квадраты В и С не ортогональны, причём ортогональность нарушена только в 9 ячейках из 100. Показываю квадрат, составленный из пар соответствующих элементов квадратов В и С: 00 77 88 99 11 22 33 44 55 66 В этом квадрате звёздочкой помечены все 18 не уникальных элементов, то есть каждый из 9 не уникальных элементов повторен. Это в некотором роде приближённое решение задачи, лучшее из известных приближений. Теперь цель - найти ещё лучшее приближение к решению задачи - так, чтобы ортогональность нарушалась менее чем в 9 ячейках. |
||
Вернуться к началу | ||
Avgust |
|
|
Если будет найдена тройка квадратов с условием ортогональности всех 100 ячеек, то что это будет означать, кроме абсолютного рекорда?
|
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Avgust писал(а): Если будет найдена тройка квадратов с условием ортогональности всех 100 ячеек, то что это будет означать, кроме абсолютного рекорда? Победу человеческого разума над нераскрытой тайной мироздания Для порядков где-то до [math]n=1000[/math], [math]n>3[/math] (кроме [math]n=6[/math]; для этого порядка даже пара ОЛК не существует) найдены группы попарно ортогональных ЛК, состоящие из 3-х и/или более квадратов. Для [math]n=3[/math] полная группа MOLS состоит из двух ЛК, то есть всего одна пара ортогональных ЛК. Для [math]n=2,[/math]так же как и для [math]n=6[/math], не существует и одна пара ОЛК. И только порядок 10 до сих пор сопротивляется. Но если ищут, то я понимаю так: несуществование тройки попарно ортогональных ЛК 10-го порядка не доказано. Если бы это доказали, то искать перестали бы. Доказали, что не существует проективной плоскости порядка 10. Это означает, что группа попарно ортогональных ЛК 10-го порядка не может состоять из 9 ЛК. Значит, она может состоять из 8 или меньше ЛК. Где-то вроде видела цифру 7, но не уверена, что-то мелькало при просмотре статей. Но даже тройку найти никак не могут. Однако ошибочную гипотезу Эйлера всё-таки опровергли. Эйлер высказал гипотезу, что для всех порядков [math]n=4k+2[/math], [math]k=1,2,3,...[/math] пары ортогональных ЛК не существуют. Гипотеза оказалась верной только для [math]n=6[/math]. Для [math]n=10[/math] гипотеза была опровергнута только в 1958 году, когда Паркер нашёл первую пару ортогональных ЛК 10-го порядка. |
||
Вернуться к началу | ||
Avgust |
|
|
Что-то гипотезы Эйлера падают и падают. Потому что тяжело было жить без компьютеров.
Но разве трудно перелолпатить все-все варианты для n=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 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 19 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |