2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 8  След.
 
 Латинские квадраты
Сообщение22.08.2008, 04:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
При рассмотрении метода построения идеальных магических квадратов с помощью орогональных латинских квадратов мне встретилась задача составления ортогонального латинского квадрата к одному обобщённому латинскому квадрату. Вот этот квадрат:
Код:
2  0  4  5  3  7  8  6  1
4  5  3  7  8  6  1  2  0
3  7  8  6  1  2  0  4  5
7  8  0  1  2  3  4  5  6
0  1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  0  1
3  4  8  6  7  2  0  1  5
8  6  7  2  0  1  5  3  4
7  2  0  1  5  3  4  8  6

При этом составленный ортогональный латинский квадрат должен быть (если смотреть на него как на нетрадиционный магический квадрат) идеальным магическим квадратом с магической константой 36 (таковым является и исходный латинский квадрат).
Мне удалось составить один латинский квадрат ортогональный данному, но он получился только ассоциативным, но не пандиагональным.
Хочется узнать, можно ли составить ортогональный латинский квадрат с нужными условиями.
Кто знает ссылки, где рассматриваются методы составления ортогональных латинских квадратов к обобщённым (а также к нормальным) латинским квадратам, напишите, пожалуйста. Я составила очень много ортогональных латинских квадратов, но как их составлять, так и не знаю :roll:
Подробности см. в статье ‹…›
Написала программу для составления нужного латинского квадрата, но она получилась "долгоиграющая", то есть очень долго выполняется; не смогла дождаться, когда она выполнится до конца.
Определения для латинских квадратов есть в Википедии в статье "Латинский квадрат", а для магических квадратов соответственно в статье "Магический квадрат".

ссылка удалена // нг

 Профиль  
                  
 
 
Сообщение24.08.2008, 09:01 
Заслуженный участник


08/04/08
8556
Я в Википедию не лазил (далее следуют сиротские ссылки на плохой диал-ап канал).
По лекциям у меня следующее.
Df1. Пусть $a_{i,j} \in {0,1,...,n-1}, i,j \in {0,1,...,n-1}$. Тогда $A=(a_{i,j})$ - ЛК (латин. квадрат) $\longleftrightarrow$
в каждой строке и каждом столбце элементы $a_{i,j}$ различны.
Df2. Наложением A&B квадратов $A=(a_{i,j}), B=(b_{i,j})$ размерности n называется квадрат
$A&B = ( (a_{i,j}, b_{i,j}) )$. (поэлементное декартово произведение).
Df3. А и В - ортогональны $\longleftrightarrow$ A&B состоит из различных элементов.


У меня есть Рыбников. Там про ЛК есть, но видимо, сложно. Могу скинуть. А так - подумать надо.

 Профиль  
                  
 
 Re: Латинские квадраты
Сообщение24.08.2008, 09:47 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak писал(а):
Кто знает ссылки, где рассматриваются методы составления ортогональных латинских квадратов к обобщённым (а также к нормальным) латинским квадратам, напишите, пожалуйста. Я составила очень много ортогональных латинских квадратов, но как их составлять, так и не знаю :roll:

Я уже как-то давал вам ссылку, повторю еще раз:
Холл М. — Комбинаторика
глава 13 там недвусмысленно там называется "Ортогональные латинские квадраты". :D

 Профиль  
                  
 
 
Сообщение25.08.2008, 05:16 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Спасибо за определения. Точно такие же определения я нашла в книге Ю. В. Чебракова.
Maxal, я смотрела по указанной вами ссылке. Но, к сожалению, прочитать интересующий меня раздел не смогла. Там написано, что скачать книгу нельзя (недвусмысленно). Тогда я поискала, как её хоть на экране монитора посмотреть, и не нашла. Вышел только Предметный указатель, в котором, да, видела: Ортогональные латинские квадраты - 244. Может быть, я что-то не увидела? :( Подскажите, пожалуйста, как же в эту книгу заглянуть?
Ну, а как насчёт моего конкретного квадратика? Есть решение? :cry:

 Профиль  
                  
 
 
Сообщение25.08.2008, 07:22 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak, забирайте отсюда:
http://eqworld.ipmnet.ru/ru/library/boo ... 970ru.djvu

 Профиль  
                  
 
 
Сообщение25.08.2008, 08:34 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
О, спасибо, Maxal! Скопировала, но ещё не посмотрела. Думаю, что очень интересный для меня материал.
А задача моя снимается. Я её только что решила. Ортогональный квадрат получен так: сначала исходный квадрат повёрнут на 90 градусов против часовой стрелки, а затем отражён относительно горизонтальной оси симметрии. Можно и так: поворот на 90 градусов по часовой стрелке с последующим отражением относительно вертикальной оси симметрии. А можно ещё проще: отражение относительно главной диагонали.
Просто вспомнила, что в самых последних моих статьях (которые написаны буквально на днях) встречается такой метод составления ортогональных латинских квадратов.
Из моей пары ортогональных латинских квадратов получился такой квадрат:
Код:
22  04  43  57  30  72  83  68  17
40  55  37  78  81  63  14  26  02
34  73  88  60  12  24  08  47  50
75  87  06  11  23  35  46  52  61
03  18  21  32  44  56  67  70  85
27  36  42  53  65  77  82  01  13
38  41  80  64  76  28  00  15  54
86  62  74  25  07  10  51  33  48
71  20  05  16  58  31  45  84  66

Кажется, этот квадрат называется греко-латинским?
Симметрия в этом квадрате изумительная. Из этого квадрата и получается идеальный магический квадрат 9-ого порядка, надо только заменить числа в девятеричной системе счисления на их десятичные эквиваленты. В этом и состоит метод построения идеальных магических квадратов с помощью двух ортогональных латинских квадратов, исследованию которого я посвятила уже несколько статей. Жаль, что здесь нельзя давать ссылки :wink:

 Профиль  
                  
 
 Применение латинских квадратов для построения МК
Сообщение01.09.2008, 13:10 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Начала писать обзорную статью о методах построения магических квадратов. Штудирую материалы по этой теме во всех источниках. Вот в книге Чебракова нахожу "Метод латинских квадратов" (Ю. В. Чебраков. Магические квадраты. Терия чисел, алгебра, комбинаторный анализ. - С.-Петербург, 1995; стр.96-97).
Цитата из книги: "Первый латинский квадрат строят следующим образом: а) произвольно заполняют нижний горизонтальный ряд квадратной таблицы n*n целыми числами от 0 до n-1, следя лишь за тем, чтобы последняя клетка горизонтального ряда была заполнена числом k=[n/2]"; б) остальные горизонтальные ряды таблицы заполняют снизу вверх так, чтобы каждый следующий ряд получался из предыдущего циклической перестановкой - первое число переносится в конец строки. Второй латинский квадрат получается из первого путём его поворота на девяносто градусов".
Ну, как строится первый латинский квадрат, понятно. В книге дана иллюстрация построения. Вот первый латинский квадрат, изображённый на иллюстрации:
Код:
2  1  4  0  3
3  2  1  4  0
0  3  2  1  4
4  0  3  2  1
1  4  0  3  2

А как составляется второй латинский квадрат, убей не понимаю! Целый час поворачивала первый латинский квадрат, но так и не смогла получить тот квадрат, который изображён на картинке у автора книги. Вот какой второй латинский квадрат дан автором:
Код:
0  3  4  1  2
3  4  1  2  0
4  1  2  0  3
1  2  0  3  4
2  0  3  4  1

Пожалуйста, объясните мне, какой здесь поворот на 90 градусов? Вокруг чего? В какую сторону?
Вот какой магический квадрат построил автор из пары составленных им ортогональных латинских квадратов:
Код:
11  9  25  2  18
19  15  7  23  1
5  17  13  6  24
22  3  16  14  10
8  21  4  20  12

Тогда я составила второй латинский квадрат по-своему: отражение первого латинского квадрата относительно горизонтальной оси симметрии. И вот какой магический (к тому же и ассоциативный; ну, ассоциативность обеспечивается удачно составленным первым латинским квадратом - он является нетрадиционным ассоциативным магическим квадратом; мой второй латинский квадрат тоже является нетрадиционным ассоциативным магическим квадратом, в отличие от второго квадрата Чебракова) квадрат получен из моей пары ортогональных латинских квадратов:
Код:
12  10  21  4  18
20  11  9  23  2
1  19  13  7  25
24  3  17  15  6
8  22  5  16  14

Если мы будем строить магический квадрат седьмого порядка по Чебракову, то как составить второй латинский квадрат? Первый латинский квадрат может быть, например, такой:
Код:
3  2  5  0  1  4  6
6  3  2  5  0  1  4
4  6  3  2  5  0  1
1  4  6  3  2  5  0
0  1  4  6  3  2  5
5  0  1  4  6  3  2
2  5  0  1  4  6  3

Правильно :?: Теперь скажите, куда и как надо повернуть на 90 градусов этот латинский квадрат, чтобы получить второй латинский квадрат по Чебракову :?:
Продолжаю проверять свой способ. Составляю второй латинский квадрат отражением первого относительно горизонтальной оси симметрии. Cтрою из полученной пары ортогональных латинских квадратов магический квадрат:
Код:
24  20  36  2  12  35  46
48  22  16  40  7  11  31
29  44  26  21  39  3  13
9  33  49  25  17  41  1
5  14  32  45  27  15  37
42  4  10  34  43  23  19
18  38  6  8  30  47  28

Магический квадрат получился.

 Профиль  
                  
 
 Re: Применение латинских квадратов для построения МК
Сообщение01.09.2008, 20:48 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak писал(а):
В книге дана иллюстрация построения. Вот первый латинский квадрат, изображённый на иллюстрации:
Код:
2  1  4  0  3
3  2  1  4  0
0  3  2  1  4
4  0  3  2  1
1  4  0  3  2

А как составляется второй латинский квадрат, убей не понимаю! Целый час поворачивала первый латинский квадрат, но так и не смогла получить тот квадрат, который изображён на картинке у автора книги. Вот какой второй латинский квадрат дан автором:
Код:
0  3  4  1  2
3  4  1  2  0
4  1  2  0  3
1  2  0  3  4
2  0  3  4  1

Пожалуйста, объясните мне, какой здесь поворот на 90 градусов? Вокруг чего? В какую сторону?

А вы точно второй квадрат отобразили? Результатом поворота на 90 градусов первого квадрата (вокруг своего центра) против часовой стрелки является:
Код:
3  0  4  1  2
0  4  1  2  3
4  1  2  3  0
1  2  3  0  4
2  3  0  4  1

 Профиль  
                  
 
 
Сообщение02.09.2008, 04:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну, поворот квадрата на 90 градусов против часовой стрелки вокруг центра - это все, наверное, знают. Второй латинский квадрат Чебракова я отобразила (скопировала из книжки) правильно. Это можно проверить по готовому магическому квадрату, который автор построил далее так (цитата):
"2. Преобразовывают полученные два латинских квадрата путём умножения каждого числа одного квадрата на n и увеличения на 1 каждого числа другого квадрата. 3. Производят поклеточно суммирование двух преобразованных на втором этапе квадратов".
Я построенный магический квадрат проверила, он построен описанным способом именно из той пары ортогональных латинских квадратов, которые приводит автор на картинке и которые мной скопированы. Готовый магический квадрат тоже здесь показан.

 Профиль  
                  
 
 
Сообщение03.09.2008, 09:26 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот ещё одна интересная пара ортогональных латинских квадратов. Я получила её при рассмотрении метода альфила (так в древние времена назывался шахматный слон).
Первый латинский квадрат:
Код:
8  3  7  2  6  1  5  0  4
3  7  2  6  1  5  0  4  8
7  2  6  1  5  0  4  8  3
2  6  1  5  0  4  8  3  7
6  1  5  0  4  8  3  7  2
1  5  0  4  8  3  7  2  6
5  0  4  8  3  7  2  6  1
0  4  8  3  7  2  6  1  5
4  8  3  7  2  6  1  5  0

Второй латинский квадрат:
Код:
4  2  0  7  5  3  1  8  6
6  4  2  0  7  5  3  1  8
8  6  4  2  0  7  5  3  1
1  8  6  4  2  0  7  5  3
3  1  8  6  4  2  0  7  5
5  3  1  8  6  4  2  0  7
7  5  3  1  8  6  4  2  0
0  7  5  3  1  8  6  4  2
2  0  7  5  3  1  8  6  4

Как здесь второй латинский квадрат получается из первого? Никакие доселе известные мне способы превращения первого латинского квадрата во второй не действуют.

 Профиль  
                  
 
 
Сообщение03.09.2008, 16:17 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Если кто-то вдруг ломает голову над "поворотом квадрата по Чебракову", можете прекратить это занятие. Чебраков допустил явный ляпсус. Я нашла разгадку этой задачи в книге М.М. Постникова, Магические квадраты, М:. Наука, 1964.Книги этой у меня нет, но один товарищ (читатель моих статей о МК) любезно прислал мне фотокопии заинтересовавшей меня главы, в которой описывается квазилинейный метод Делаира. Постников не называет квадраты, участвующие в построении магических квадратов, латинскими, он называет их вспомогательными, но сути дела это не меняет. Посмотрев приведённый Постниковым пример построения магического квадрата 5-ого порядка с помощью двух вспомогательных (=латинских) квадратов, я всё поняла. Подробности изложу в статье.

 Профиль  
                  
 
 
Сообщение05.09.2008, 08:11 
Заслуженный участник


08/04/08
8556
Можно вопрос? Для данного латинского квадрата сколько существует ортогональных?

 Профиль  
                  
 
 
Сообщение05.09.2008, 15:09 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вы имеете в виду латинский квадрат 5-ого порядка Чебракова? Думаю, что как минимум 24 ортогональных латинских квадрата для него существуют. Два я уже показала здесь, один Чебраковский, другой мой. Дело в том, что по методу Делаира второй вспомогательный (=латинский) квадрат не получается из первого никакими поворотами. Он строится самостоятельно по правилу, аналогичному построению первого латинского квадрата, только произвольная перестановка чисел вписывается не в нижнюю, а в верхнюю строку. Я уже изложила метод Делаира в статье "Методы построения магических квадратов".

 Профиль  
                  
 
 Задача о латинском квадрате
Сообщение08.09.2008, 15:14 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Рассматривая в статье “Методы построения магических квадратов” метод окаймлённых квадратов, заинтересовалась концентрическими магическими квадратами. Построение таких квадратов привело меня к такому латинскому квадрату, который составлен только наполовину. Требуется достроить этот обобщённый латинский квадрат и, если решение есть, построить к нему ортогональный латинский квадрат. Латинский квадрат такой:
Код:
5  6  7  8  0  1  2  3  4
6  a  b  c  d  e  f  g  2
7  x  1  6  8  4  1  x’ 1
8  y  2  3  5  4  6  y’ 0
0  z  8  5  4  3  0  z’ 8
1  w  2  4  3  5  6  w’ 7
2  t  7  2  0  4  7  t’ 6
3  g’ b’ c’ d’ e’ f’ a’ 5
4  2  1  0  8  7  6  5  3

Переменные с апострофом комплементарны соответствующим переменным без апострофа, например: a+a’=8.
Не уверена, что решение существует, но очень хочется, чтобы существовало :?

 Профиль  
                  
 
 
Сообщение08.09.2008, 17:19 


02/09/08
143
Просто латинский квадрат построить легко: a=4,b=7,c=7,d=2,e=0,f=5,g=3,x=0,y=1,z=6,w=8,t=3.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 111 ]  На страницу 1, 2, 3, 4, 5 ... 8  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group