Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 3956 ]  На страницу 1, 2, 3, 4, 5 ... 396  След.
Автор Сообщение
 Заголовок сообщения: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 13:38 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 23:27
Сообщений: 4376
Откуда: Саратов
Cпасибо сказано: 518
Спасибо получено:
288 раз в 242 сообщениях
Очков репутации: 94

Добавить очки репутацииУменьшить очки репутации
Определение латинского квадрата можно посмотреть в статье Википедии "Латинский квадрат".

В дальнейшем вместо "латинский квадрат" для краткости будем использовать аббревиатуру ЛК.
Сразу замечу, что здесь будут рассматриваться классические ЛК 10-го порядка. Есть ещё обобщённые ЛК, которые здесь не рассматриваются.

Пример ЛК 10-го порядка

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

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

В приведённом выше примере это свойство выполняется только в одной главной диагонали.

Пример диагонального ЛК 10-го порядка

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

Определение 2
два ЛК называются ортогональными, если все пары, составленные из элементов соответствующих ячеек ЛК, различны.

Пример пары ортогональных ЛК 10-го порядка

квадрат №1
0 4 1 7 2 9 8 3 6 5
8 1 5 2 7 3 9 4 0 6
9 8 2 6 3 7 4 5 1 0
5 9 8 3 0 4 7 6 2 1
7 6 9 8 4 1 5 0 3 2
6 7 0 9 8 5 2 1 4 3
3 0 7 1 9 8 6 2 5 4
1 2 3 4 5 6 0 7 8 9
2 3 4 5 6 0 1 8 9 7
4 5 6 0 1 2 3 9 7 8

квадрат №2
0 7 8 6 9 3 5 4 1 2
6 1 7 8 0 9 4 5 2 3
5 0 2 7 8 1 9 6 3 4
9 6 1 3 7 8 2 0 4 5
3 9 0 2 4 7 8 1 5 6
8 4 9 1 3 5 7 2 6 0
7 8 5 9 2 4 6 3 0 1
4 5 6 0 1 2 3 7 8 9
1 2 3 4 5 6 0 9 7 8
2 3 4 5 6 0 1 8 9 7

Это знаменитая пара Паркера.
(см. статью "Ортогональные латинские квадраты 10-го порядка")

Квадрат, составленный из пар чисел, образованных элементами двух данных ЛК:

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

Этот квадрат называют греко-латинским квадратом или квадратом Эйлера.
Интересно, что для порядка 10 греко-латинский квадрат - уже готовый магический квадрат. Разве что для более привычного традициооного вида магического квадрата можно увеличить все элементы на единицу.

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 15:47 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 23:27
Сообщений: 4376
Откуда: Саратов
Cпасибо сказано: 518
Спасибо получено:
288 раз в 242 сообщениях
Очков репутации: 94

Добавить очки репутацииУменьшить очки репутации
Просматривая недавно Гостевую книгу своего сайта, наткнулась на сообщение от 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
7 1 9 4 5 3 8 0 6 2
4 6 2 8 3 1 7 5 9 0
6 0 7 3 2 8 4 9 1 5
5 3 6 7 4 2 9 1 0 8
8 4 1 2 9 5 0 6 3 7
2 5 3 0 8 9 6 4 7 1
3 2 8 9 0 4 1 7 5 6
9 7 5 1 6 0 3 2 8 4
1 8 0 5 7 6 2 3 4 9

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

Ещё две пары смотрите в указанной статье.

Итак, одной из задач, решаемых в проекте, является задача поиска пар ортогональных диагональных ЛК 10-го порядка (сокращённо - ОДЛК).
По ссылке
http://sat.isa.ru/pdsat/solutions.php
вы можете посмотреть результаты поиска. Самая последняя пара ОДЛК была найдена 13.01.2016 г.
Вот она:
№1

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

№2

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 17:00 
Не в сети
Мастер
Зарегистрирован:
24 янв 2013, 22:19
Сообщений: 216
Cпасибо сказано: 54
Спасибо получено:
15 раз в 15 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak писал(а):
Поиск тройки попарно ортгональных ЛК 10-го порядка вели в прошлом веке и продолжают вести в веке нынешнем. До сих пор такая тройка не найдена.

По памяти, в 2004-2007 годах откуда-то в инете взял тройку попарно орт. лат. квадратов то ли 10 -го порядка, то ли 12-го и по своей методе искал в ней выход на 4-ый квадрат, но увы. Однако, записи не выбросил и точно они сохранились.
Не могу покамест себя заставить переворушить горы, десятки кг. черновиков.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 20:46 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 23:27
Сообщений: 4376
Откуда: Саратов
Cпасибо сказано: 518
Спасибо получено:
288 раз в 242 сообщениях
Очков репутации: 94

Добавить очки репутацииУменьшить очки репутации
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 год)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 21:22 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 23:27
Сообщений: 4376
Откуда: Саратов
Cпасибо сказано: 518
Спасибо получено:
288 раз в 242 сообщениях
Очков репутации: 94

Добавить очки репутацииУменьшить очки репутации
Нашла в Интернете ссылку на статью "Поиск систем ортогональных латинских квадратов в проекте добровольных вычислений 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).
Цель – получить новый рекорд.

Два дня назд Олег прислал мне ссылку на статью, содержащую рекордную псевдотройку.
Далее я покажу эту псевдотройку.
Псевдотройки, найденные в проекте, вы можете посмотреть по приведённой в стартовом сообщении ссылке.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 21:39 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 23:27
Сообщений: 4376
Откуда: Саратов
Cпасибо сказано: 518
Спасибо получено:
288 раз в 242 сообщениях
Очков репутации: 94

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak писал(а):
Интересно, что для порядка 10 греко-латинский квадрат - уже готовый магический квадрат. Разве что для более привычного традициооного вида магического квадрата можно увеличить все элементы на единицу.

Уточнение: конечно, магический квадрат получится из греко-латинского квадрата, составленного из элементов пары ортогональных диагональных ЛК. Если же ЛК не диагональные, то получится полумагический квадрат (не будет нужной суммы чисел в одной или в обеих главных диагоналях квадрата).
Очень редко бывают случаи, когда ортогональные ЛК не диагональные, но магический квадрат дают; это тогда, когда сумма элементов в обеих главных диагоналях ЛК равна сумме элементов в строках и столбцах ЛК.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 23:38 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 23:27
Сообщений: 4376
Откуда: Саратов
Cпасибо сказано: 518
Спасибо получено:
288 раз в 242 сообщениях
Очков репутации: 94

Добавить очки репутацииУменьшить очки репутации
Итак, ссылка на статью, содержащую недавно найденную рекордную псевдотройку
http://www.ams.org/journals/mcom/2016-8 ... 3010-5.pdf

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

квадрат А

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

квадрат В

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

квадрат С

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

Квадраты А и В ортогональны, квадраты А и С ортогональны, а квадраты В и С не ортогональны, причём ортогональность нарушена только в 9 ячейках из 100.
Показываю квадрат, составленный из пар соответствующих элементов квадратов В и С:

00 77 88 99 11 22 33 44 55 66
96 04 62 18* 89* 35 21 53 47 70
74 29* 05 43 32 97* 16 80 61 58
85 51 37* 06 24 13 78* 69 90 42
63 92 59* 30 07 71 45 26 18* 84
41 10 73 67* 56 08 82 95 34 29*
52 48* 20 81 93 64 09 37* 76 15
39 65 14 72 48* 86 50 01 23 97*
17 83 46 25 60 59* 94 78* 02 31
28 36 91 54 75 40 67* 12 89* 03

В этом квадрате звёздочкой помечены все 18 не уникальных элементов, то есть каждый из 9 не уникальных элементов повторен.
Это в некотором роде приближённое решение задачи, лучшее из известных приближений.
Теперь цель - найти ещё лучшее приближение к решению задачи - так, чтобы ортогональность нарушалась менее чем в 9 ячейках.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 18 янв 2016, 00:59 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 20:13
Сообщений: 9806
Откуда: Москва
Cпасибо сказано: 903
Спасибо получено:
3027 раз в 2630 сообщениях
Очков репутации: 609

Добавить очки репутацииУменьшить очки репутации
Если будет найдена тройка квадратов с условием ортогональности всех 100 ячеек, то что это будет означать, кроме абсолютного рекорда?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 18 янв 2016, 07:04 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 23:27
Сообщений: 4376
Откуда: Саратов
Cпасибо сказано: 518
Спасибо получено:
288 раз в 242 сообщениях
Очков репутации: 94

Добавить очки репутацииУменьшить очки репутации
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-го порядка.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 18 янв 2016, 10:08 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 20:13
Сообщений: 9806
Откуда: Москва
Cпасибо сказано: 903
Спасибо получено:
3027 раз в 2630 сообщениях
Очков репутации: 609

Добавить очки репутацииУменьшить очки репутации
Что-то гипотезы Эйлера падают и падают. Потому что тяжело было жить без компьютеров.
Но разве трудно перелолпатить все-все варианты для n=10 ? Ведь именно так была доказана задача о четырех красках.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 3956 ]  На страницу 1, 2, 3, 4, 5 ... 396  След.

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Идеальные магические квадраты

в форуме Размышления по поводу и без

Avgust

74

1817

22 ноя 2015, 09:15

Разбиение треугольника на квадраты и треугольнички

в форуме Геометрия

Avgust

100

1242

18 ноя 2016, 16:26

Квадраты, обобщение числа пи и таинственная гамма-функция

в форуме Теория чисел

ivashenko

4

302

01 мар 2016, 21:35

Точки и квадраты. Возможно ли рассчитать шансы на выигрыш?

в форуме Теория вероятностей

Lord-Vadim

0

125

29 окт 2015, 13:27

Ортогональные векторы

в форуме Аналитическая геометрия и Векторная алгебра

Alex03889

1

125

23 дек 2012, 16:00

Ортогональные пространства

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

Avrora

0

126

18 ноя 2014, 19:53

Выделить полные квадраты получ каноническое уравнен квадрики

в форуме Линейная и Абстрактная алгебра

Haggard

12

1809

12 янв 2012, 03:24

Ряд Фурье и другие ортогональные разложения

в форуме Ряды Фурье и Интегральные преобразования

Chelovekley

1

219

29 апр 2015, 15:47

Ортогональные центральные композиционный план

в форуме Исследование операций и Задачи оптимизации

AHAHAC

2

95

08 дек 2016, 10:20

Левое и правое ортогональные дополнения подпространства

в форуме Линейная и Абстрактная алгебра

TotalRecall

2

315

30 апр 2012, 02:18


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved