Магические квадраты

[maxal]

Nataly-Mak в сообщении #167742 писал(а):

Кто с Maple на "ты", скажите, пожалуйста, он умеет строить только одну группу для каждого конкретного порядка?

Я уже вам отвечал - только одну.

Nataly-Mak в сообщении #167742 писал(а):

И ещё желательно получить ответ на вопрос: может ли Maple построить ортогональный латинский квадрат к данному.

Не умеет, и мы это уже тоже обсуждали ранее. И вообще построение ортогонального квадрата к заданному - это сложная вычислительная задача, для которой ничего быстрее перебора (возможно, немного оптимизированного) не придумано.

[Nataly-Mak]

maxal писал(а):

Я уже вам отвечал - только одну.

Извините, но я такого ответа не припомню (возможно, это было в теме "Латинские квадраты", которую я с некоторого времени перестала просматривать). Помню, что я задавала вопрос: является ли построенная группа ортогональных латинских квадратов (например, 8-го порядка) единственной. Вы ответили, что не является. Значит, есть другие группы? Я правильно понимаю? А если есть другие группы, то почему Maple их не может строить? Это непонятно. Просто недоработка соответствующей программы?
Теперь по вопросу построения ортогонального квадрата к заданному. Если это сложная вычислительная задача, то кому как не пакету математических программ её решать. Однако я не уверена, что здесь нет других алгоритмов. Вот, например, в статье (о которой я недавно рассказала), приведены 3 ортогональных латинских квадрата 22-го порядка. Почти уверена, что авторы тут применили не простой перебор, а какой-то чёткий алгоритм составления таких квадратов. То же самое и для найденных вами ортогональных латинских квадратов 10-го порядка.
Разработчикам Maple здесь есть о чём подумать.
А ещё предлагаю ввести в пакет программ программу построения магических квадратов методом латинских квадратов. Такого ведь Maple сейчас не делает? Ведь если он строит ортогональные латинские квадраты, то ничего не стоит сделать незначительные добавления в программу, и с помощью этих латинских квадратов будут строиться магические квадраты любого порядка, для которого Maple может составлять ортогональные латинские квадраты.

[maxal]

Nataly-Mak в сообщении #167777 писал(а):

Помню, что я задавала вопрос: является ли построенная группа ортогональных латинских квадратов (например, 8-го порядка) единственной. Вы ответили, что не является. Значит, есть другие группы? Я правильно понимаю? А если есть другие группы, то почему Maple их не может строить? Это непонятно. Просто недоработка соответствующей программы?

Скорее всего есть (но я в деталях не проверял). А не строит - потому что, вероятно, такой задачи разработчики мапла перед собой не ставили. Наборы попарно ортогональных квадратов полезны в некоторых прикладных задачах типа планирования экспериментов (вроде примеры где-то тут тоже приводили), но в них обычно требуется лишь один набор таких квадратов - вот мапл один такой набор и строит.

Nataly-Mak в сообщении #167777 писал(а):

Если это сложная вычислительная задача, то кому как не пакету математических программ её решать.

Если нет эффективных алгоритмов решения, то никакой матпакет не поможет. Представьте, например, что мапл умел бы эту задачу решать за обозримое время лишь для квадратов порядка до 10, а решение для квадратов порядка 20 уже требовало бы года вычислений - ну и кому такое решение нужно?

Nataly-Mak в сообщении #167777 писал(а):

Однако я не уверена, что здесь нет других алгоритмов. Вот, например, в статье (о которой я недавно рассказала), приведены 3 ортогональных латинских квадрата 22-го порядка. Почти уверена, что авторы тут применили не простой перебор, а какой-то чёткий алгоритм составления таких квадратов.

Они решали другую задачу. Не забывайте, что мы говорим о построении ортогонального квадрата к данному, а не о построении (абы какого) набора ортогональных квадратов.

Nataly-Mak в сообщении #167777 писал(а):

А ещё предлагаю ввести в пакет программ программу построения магических квадратов методом латинских квадратов. Такого ведь Maple сейчас не делает?

Не делает, и скорее всего потому, что на такую функцию очень небольшой спрос. Кроме того, ее просто реализовать на языке самого мапла - вовсе необязательно встраивать ее в сам пакет.

[Nataly-Mak]

maxal писал(а):

Они решали другую задачу. Не забывайте, что мы говорим о построении ортогонального квадрата к данному, а не о построении (абы какого) набора ортогональных квадратов.

Очень тонкий момент! Но я всё-таки хочу понять... Что значит "абы какого набора ортогональных квадратов"? Если они (то бишь авторы этих двух статей) знают, как составлять взаимно ортогональные квадраты (ведь они же составили три взаимно ортогональных квадрата), значит, они знают КАК составить ортогональный квадрат к данному квадрату. Или нет?

[maxal]

Nataly-Mak в сообщении #167790 писал(а):

Если они (то бишь авторы этих двух статей) знают, как составлять взаимно ортогональные квадраты (ведь они же составили три взаимно ортогональных квадрата), значит, они знают КАК составить ортогональный квадрат к данному квадрату. Или нет?

Вот именно, что нет. То, что они сумели найти какую-то одну тройку попарно ортогональных квадратов, не означает, что они могут найти квадрат ортогональный к данному.
Другими словами, если бы вы попросили их найти тройку (или даже пару) попарно ортогональных квадратов, содержащую некоторый фиксированный квадрат, то они, скорее всего, не сумели бы этого сделать.
Например, квадраты из построенной ими тройки могут обладать некоторым дополнительным свойством, на котором и основывается все их построение, а вот данный фиксированный квадрат этим свойством не обладать - и что с ним делать будет непонятно.

[Nataly-Mak]

Ага! Кажется, начинаю понимать. Они могут построить ортогональный квадрат к очень конкретному исходному квадрату. А к другому исходному квадрату по такому же алгоритму, пожалуй, и не смогут построить ортогональный квадрат. Но другой исходный квадрат нам пока и взять негде.
Можно ещё вопрос? Если мы берём два ортогональных латинских квадрата и преобразовываем их (как я это сделала с латинскими квадратами 22-го порядка), и преобразование это состоит в трансформации тождественной перестановки чисел 0, 1, 2 … 21 в другую перестановку (причём для каждого квадрата это своя трансформация), можно ли быть уверенным в том, что преобразованные квадраты тоже будут ортогональны? В указанном примере преобразованные ЛК получились ортогональными.

[Aleks-Sid]

Nataly-Mak

Цитата:

Больший интерес представляет вторая пара ортогональных диагональных латинских квадратов 5-го порядка. Эту пару составил maxal. Он установил, что для порядка 5 существуют только две пары ортогональных диагональных латинских квадратов. Вот эта пара:
0 1 2 3 4
4 2 3 0 1
3 4 1 2 0
1 3 0 4 2
2 0 4 1 3

0 1 2 3 4
3 4 1 2 0
4 2 3 0 1
2 0 4 1 3
1 3 0 4 2

Вот забавно! Какой умный maxal! Но у меня есть свое решение (с помощью цепей Александрова) и оно более изящное:

1 5 4 3 2
3 2 1 5 4
5 4 3 2 1
2 1 5 4 3
4 3 2 1 5

1 3 5 2 4 
5 2 4 1 3
4 1 3 5 2
3 5 2 4 1
2 4 1 3 5

Изящней потому, что получается не просто МК, а идеальный МК (то есть числа не повторяются ни в одной ломаной диагонали. В отличие от цитируемого варианта). Да и метод совершенно прозрачный и годится для любого n=2k+1, не кратного 3. Первая матрица транспонируется - и все дела! Сама же первая матрица - суть цикличная цепочка, которая от строки к строке идет со сдвигом на две ячейки.

[Nataly-Mak]

Aleks-Sid писал(а):

Но у меня есть свое решение (с помощью цепей Александрова) и оно более изящное

"Ваше" решение приведено в книге М. Гарднера "Математические досуги" (М.: Мир, 1972 г.) на стр. 9. в нормализованном виде (обратите внимание: 1972 год!)
Это есть вторая пара ортогональных диагональных латинских квадратов (плюс к той, что нашёл maxal). Использование этой пары для построения магических квадратов изложено также в книге Ю. В. Чебракова (1995 год!). Это и есть метод коня или метод Москопула, который известен вообще до Всемирного потопа.
А вы всё говорите о каком-то своём решении.

[Aleks-Sid]

Мне важно, что я его сам нашел и натренировал свое мышление. Это говорит о многом, например, о том, что умею правильно и красиво решать другие задачи. В отличие от некоторых.
По поводу дат. Я магическими квадратами занимался еще в школе (она с математическим уклоном и приходилось участвовать в разных конкурсах). В десятом классе (это был 1966 год) как раз и построил приведенный выше пример. Только не знал, что он идеальный. О публикациях тогда и речи не могло быть, так как даже печатную машинку в те далекие шестидесятые дома никто не имел права держать без необходимой регистрации.

P.S. Я вот вспоминаю, как Вы раскритиковали этого коня! Боже мой! Какой визг стоял! Жаль будет, если уберете со своих дневников ту огульную критику.

[maxal]

Aleks-Sid в сообщении #167822 писал(а):

Вот забавно! Какой умный maxal!

Aleks-Sid в сообщении #167850 писал(а):

Мне важно, что я его сам нашел и натренировал свое мышление. Это говорит о многом, например, о том, что умею правильно и красиво решать другие задачи. В отличие от некоторых.

Aleks-Sid, я вас предупреждал. За постоянные выпады в сторону других участников форума и бахвальство перевожу вас в режим чтения. Пока лишь на неделю, но если не сделаете из этого инцидента соответствующих выводов, лишитесь права писать в этот форум навсегда.

[Nataly-Mak]

Aleks-Sid писал(а):

Я вот вспоминаю, как Вы раскритиковали этого коня!

Необходимо сделать уточнение.
Я критиковала совсем не “этого коня”, то есть не метод коня (метод Москопула), который работает для построения магических квадратов любого нечётного порядка. В этом методе всё чётко и критиковать его не за что.
Моя критика относилась к методу цепей для построения идеальных магических квадратов нечётных порядков кратных 3 [n = 3(2k + 1), k = 1, 2, 3 …].

[maxal]

Вот простенькая программка на PARI/GP, которая строит полустроки для любого заданного четного порядка n:

{ semirows(n) = local(x,v);
if(n%2,error("Odd n")); 
if(n%8==0 || n%8==6, 
  x=n/2; v=vector(n/2,i,i); 
  , 
  x=n/2+1; v=vector(n/2,i,if(i==n/2,i+1,i));
); 
s=sum(j=1,#v,v[j])/2; 
forstep(j=#v,1,-1,
  if(s>=v[j], s-=v[j]; v[j]+=x, v[j]=x-v[j]);
); 
[v,vector(#v,i,2*x-v[i])]
}

Стоит заметить, что если $n$ при делении на 8 дает в остатке 0 или 6, то построенные полустроки содержает в точности числа от 0 до n, за исключением n/2. Если n дает в остатке 2 или 4, то такое невозможно - в этом случае построенные полустроки содержат числа от 0 до n+2, за исключением 1, n/2+1 и n+1.

Примеры полустрок для n в интервале от 10 до 30:

? forstep(n=10,30,2,print("n=",n,": ",semirows(n)))
n=10: [[5, 8, 3, 2, 12], [7, 4, 9, 10, 0]]
n=12: [[6, 5, 4, 11, 2, 14], [8, 9, 10, 3, 12, 0]]
n=14: [[8, 5, 4, 3, 2, 13, 14], [6, 9, 10, 11, 12, 1, 0]]
n=16: [[7, 6, 11, 4, 3, 2, 15, 16], [9, 10, 5, 12, 13, 14, 1, 0]]
n=18: [[9, 8, 7, 6, 15, 4, 3, 18, 20], [11, 12, 13, 14, 5, 16, 17, 2, 0]]
n=20: [[10, 9, 8, 7, 6, 5, 4, 19, 20, 22], [12, 13, 14, 15, 16, 17, 18, 3, 2, 0]]
n=22: [[10, 9, 14, 7, 6, 5, 4, 3, 20, 21, 22], [12, 13, 8, 15, 16, 17, 18, 19, 2, 1, 0]]
n=24: [[11, 10, 9, 8, 7, 18, 5, 4, 3, 22, 23, 24], [13, 14, 15, 16, 17, 6, 19, 20, 21, 2, 1, 0]]
n=26: [[13, 12, 11, 10, 9, 8, 7, 6, 23, 4, 25, 26, 28], [15, 16, 17, 18, 19, 20, 21, 22, 5, 24, 3, 2, 0]]
n=28: [[14, 17, 12, 11, 10, 9, 8, 7, 6, 5, 26, 27, 28, 30], [16, 13, 18, 19, 20, 21, 22, 23, 24, 25, 4, 3, 2, 0]]
n=30: [[14, 13, 12, 11, 10, 21, 8, 7, 6, 5, 4, 27, 28, 29, 30], [16, 17, 18, 19, 20, 9, 22, 23, 24, 25, 26, 3, 2, 1, 0]]

[Nataly-Mak]

maxal
Блестящее решение! Вы сделали даже для любого чётного n, а надо только для n=4k+2.
Вы спрашивали, почему X должно быть чётным. Дело в том, что магическая константа латинского квадрата S=X*n/2. n/2 число нечётное, если Х тоже будет нечётное, то и магическая константа будет число нечётное. Но тогда как найти сумму в полустроках, которая равна S/2?
А я собиралась сообщить о другом замечательном решении задачи, найденном ещё одним участником форума. Не успела! Но обязательно покажу это решение. Оно отличается от вашего решения. Более того, автор решения составил уже программу для составления нетрадиционных идеальных магических квадратов любого порядка n=4k+2 на Фортране и прислал её мне. Он пишет, что по программе можно строить МК до порядка 9998! И только следующий 10002 порядок у него не получился, нужная память превысила 2 Гб.

[maxal]

Nataly-Mak
Да, для n вида 4k+2, X не может быть нечетным, но если n делится на 4 - то почему бы и нет?
Хочу заметить, что моя программа требует линейного по n времени и памяти. Ради интереса вычислил полустроки для n равного миллиону - весь расчёт занял около секунды.

[Nataly-Mak]

maxal
А квадрат какого максимального порядка вы можете построить по своей программе? Имеется в виду магический квадрат, он строится из двух латинских квадратов, для которых эти полустроки и составляются.