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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 4210 ]  На страницу 1, 2, 3, 4, 5 ... 421  След.
Автор Сообщение
 Заголовок сообщения: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 12:38 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

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

В дальнейшем вместо "латинский квадрат" для краткости будем использовать аббревиатуру ЛК.
Сразу замечу, что здесь будут рассматриваться классические ЛК 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, 14:47 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
Просматривая недавно Гостевую книгу своего сайта, наткнулась на сообщение от 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, 16:00 
Не в сети
Мастер
Зарегистрирован:
24 янв 2013, 21:19
Сообщений: 278
Cпасибо сказано: 153
Спасибо получено:
17 раз в 17 сообщениях
Очков репутации: 1

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 19:46 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
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, 20:22 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
Нашла в Интернете ссылку на статью "Поиск систем ортогональных латинских квадратов в проекте добровольных вычислений 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, 20:39 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 17 янв 2016, 22:38 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
Итак, ссылка на статью, содержащую недавно найденную рекордную псевдотройку
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-го порядка
СообщениеДобавлено: 17 янв 2016, 23:59 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13534
Откуда: Москва
Cпасибо сказано: 1290
Спасибо получено:
3616 раз в 3175 сообщениях
Очков репутации: 678

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 18 янв 2016, 06:04 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
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, 09:08 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13534
Откуда: Москва
Cпасибо сказано: 1290
Спасибо получено:
3616 раз в 3175 сообщениях
Очков репутации: 678

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

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
О теме "Отрогональные латинские квадраты 10-го порядка"

в форуме Предложения, Замечания, Обратная связь

Nataly-Mak

21

2543

14 июн 2018, 05:28

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

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

Avrora

0

330

18 ноя 2014, 18:53

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

в форуме Векторный анализ и Теория поля

kala12

2

236

02 ноя 2021, 15:04

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

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

HJey

0

224

18 апр 2019, 23:18

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

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

AHAHAC

2

463

08 дек 2016, 09:20

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

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

Chelovekley

1

485

29 апр 2015, 14:47

Обобщенные вещественно ортогональные формы в радиосвязи

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

mike84

2

557

14 июн 2015, 13:37

Квадраты

в форуме Интересные задачи участников форума MHP

Krash

20

741

18 июл 2021, 17:46

Доказать, что ортогональные проекции вершин н-мерного куба

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

Arzybek

13

456

18 сен 2020, 21:29

Квадраты в окружности

в форуме Начала анализа и Другие разделы школьной математики

nerzul88

8

561

20 май 2020, 09:48


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



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

Сейчас этот форум просматривают: ferma-T и гости: 2


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

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

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

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