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

[svb]

Pavlovsky в сообщении #373903 писал(а):

Предлагаю для конкурса еще задачу:
Даны числа (первая колонка число, втарая количество таких чисел):
0 30
1 1
2 1
3 4
4 35
6 32
8 6

Используя эти числа построить пандиагональный МК 6х6 такой что:
1) Сумма чисел в любой строке, колонке, диагонали, разорванной диагонали была одинаковой по модулю 9.

Может я что-то не понял?

 6  8  4  6  6  6
 4  6  6  8  6  6
 8  6  6  4  6  6
 6  4  8  6  6  6
 6  6  6  6  6  6
 6  6  6  6  6  6

 0  3  6  0  0  0
 6  0  0  3  0  0
 3  0  0  6  0  0
 0  6  3  0  0  0
 0  0  0  0  0  0
 0  0  0  0  0  0

 6  8  4  6  6  6
 4  6  6  8  6  6
 8  6  6  6  4  6
 6  4  6  6  6  8
 6  6  8  6  6  4
 6  6  6  4  8  6

 0  6  3  0  6  3
 0  0  0  0  0  0
 0  0  0  0  0  0
 0  3  6  0  3  6
 0  0  0  0  0  0
 0  0  0  0  0  0

И т.п.

[Nataly-Mak]

А я всё мучаю смитов
Ничего не получается. Удалось выжать максимальный примитивный прямоугольник 8х7:

166 526 562 778 22738 442318 560506
1282 1642 1678 1894 23854 443434 561622
1822 2182 2218 2434 24394 443974 562162
1966 2326 2362 2578 24538 444118 562306
3802 4162 4198 4414 26374 445954 564142
45022 45382 45418 45634 67594 487174 605362
170266 170626 170662 170878 192838 612418 730606
234382 234742 234778 234994 256954 676534 794722

Это получилось смешанным достраиванием.
Попыталась достроить к этому прямоугольнику хотя бы один столбец "чистым" достраиванием, не получилось. Явно смитов мне не хватает.

[Pavlovsky]

svb
Все правильно понял. А вот у меня так быстро не получилось. Ты как ручками строил? Или програмно?

[Nataly-Mak]

Pavlovsky
просмотрела форум, нашла: на стр. 119 я сообщала о шаблонах для пандиагональных квадратах 6-го порядка из смитов по модулю 9. Там написано, что я делала программу для шаблонов с вычетами 0, 3, 4, 6, 8. Только я не оганичивала количество вычетов.
Там приведены такие два шаблона:

8  3  0  3  0  4 
6  0  3  3  3  3 
4  0  3  0  3  8 
6  3  8  4  6  0 
3  3  0  0  6  6 
0  0  4  8  0  6 

8  6  0  0  0  4 
3  0  3  3  6  3 
4  0  3  0  3  8 
0  3  8  4  3  0 
3  0  0  3  6  6 
0  0  4  8  0  6

И шаблонов программа выдавала море. Там были разные, из разных вычетов.
Программу я делала по общей формуле для пандиагонального квадрата 6-го порядка, которая тоже здесь была приведена.
Посколько вычетов немного, программа выполняется довольно быстро.

Далее я выбрала шаблон без троек, то есть состоящий из вычетов 0, 4, 6, 8, и делала программу построения пандиагонального квадрата по этому шаблону.
А потом в эту программу вводила смиты только с вычетом 4. Но поскольку я брала много чисел, программа очень долго выполнялась, я так и не выполнила её до конца. Я брала 4 группы смитов (соответственно 4 группам вычетов) по 36 чисел в каждой группе.
Но если брать, например, маленькие магические константы, то и чисел в массиве будет не так много.
Более того, можно экспериментировать с потенциальными массивами, состоящими точно из 36 чисел. Тогда в каждой группе можно задать не 36 чисел, а, скажем, по 10-12 штук. В этом случае программа должны намного быстрее работать.
Я тогда прервала работу со своей программой, потому что svb предложил новый алгоритм, который дал неплохие результаты. Однако до наименьшего квадрата из смитов мы так и не добрались.
А впрочем, может быть, и добрались. Ещё не доказано, что квадрат с магической константой 5964 не является наименьшим.

Да, задача эта включена в конкурсные задачи.
Так что, если вы вдруг найдёте решение, не публикуйте его, шлите мне в личку.

[Nataly-Mak]

Участникам конкурса "Нетрадиционные пандиагональные квадраты"

Обратите внимание!

Сегодня утром в объявление о конкурсе было добавлено одно условие. Виновата, забыла написать сразу. Хотя это явствует из всех приведённых примеров, тем не менее это условие обязательно должно присутствовать.

Условие вставлено в самом начале, перед задачами:

Общее требование ко всем задачам: каждый построенный квадрат должен состоять из различных чисел.

Пока решений не прислано, и условие вовремя добавлено.

[svb]

Pavlovsky в сообщении #374492 писал(а):

Ты как ручками строил? Или програмно?

Да практически в уме. Я же уже давно с этими элементами

 0  1 -1  0
-1  0  0  1
 1  0  0 -1 
 0 -1  1  0  

кручусь. Потому и удивился - ты, вроде, читал мои заметки.

[Nataly-Mak]

Я задавала выше вопрос по этой же задаче, мне никто не ответил.

Брала какую-то из магических констант (меньше 5964, не помню сейчас точное значение) и пыталась сформировать потенциальный массив из 36 смитов равных 4(mod 9), дающий эту магическую константу, случайной генерацией и ещё по программе формирования массива.
Ни тот, ни другой способ мне не дал массива!

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

Вот и вопрос:
для любой ли магической константы существует потенциальный массив из 36 смитов равных 4(mod 9)?

[svb]

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

Приведу аналогию из теории чисел. Имеется утверждение: положительное целое число можно представить в виде суммы двух квадратов тогда и только тогда, когда все простые сомножители вида $4k+3$ входят в каноническое разложение этого числа с четными показателями. Это утверждение обычно называется теоремой Ферма. Г.Харди называл ее одной из красивейших в теории чисел.

Вполне возможно, особенно в наше время, представить себе ситуацию, когда после конкретных численных экспериментов исследователь выходит это утверждение. Я даже уверен, что история теоремы Ферма с этого и начиналась. Но это могло явиться только стимулом для поиска глубинных причин подобной связи между столь внешне разнородными объектами, как сумма квадратов и разложение на простые сомножители.

Красота и неожиданность математики именно в подобных связях. Как их обнаруживать и, тем более, доказывать до сих пор никто не знает. Применительно к таким объектам, как магические квадраты, можно сказать то же самое. Мало просто любоваться на конкретный "красивый" квадрат, исследователя всегда должен мучить вопрос "почему?". Иногда стоит отойти от основной задачи и попытаться в наиболее общем виде решить некоторое "ответвление", для которого может быть найдется решение. С одним из таких ответвлений мы уже постоянно сталкиваемся - рассмотрение квадратов в кольце вычетов (хотя бы по модулю 2). При рассмотрении этой "простенькой" задачи есть шанс приоткрыть тайну "критериев для наборов".

На данном форуме или на каком-либо другом, как мне кажется, полезно было бы собирать вопросы, относящиеся к "общим". К ним, например, относятся и "методы построения" частных случаев квадратов, которые много лет собирает Наталия.

[Nataly-Mak]

Задействовав смиты до 10^7, получила примитивный квадрат 8х8 по алгоритму смешанного достраивания:

58  382  2038  5242  302098  2301898  2508358  2995042 
 202  526  2182  5386  302242  2302042  2508502  2995186 
 454  778  2434  5638  302494  2302294  2508754  2995438 
 634  958  2614  5818  302674  2302474  2508934  2995618 
 274234  274558  276214  279418  576274  2576074  2782534  3269218 
 652378  652702  654358  657562  954418  2954218  3160678  3647362 
 2570278  2570602  2572258  2575462  2872318  4872118  5078578  5565262 
 3062182  3062506  3064162  3067366  3364222  5364022  5570482  6057166

Осталось достроить 3 строки и 3 столбца, чтобы получить примитивный квадрат 11х11.
Думаю, что для достраивания не хватит и смитов в указанном интервале.
Очень плохо ведут себя смиты
Придётся отложить задачу построения пандиагонального квадрата 11-го порядка из смитов.

Кстати, вот здесь maxal выложил по моей просьбе смиты до 10^7, может быть, кому надо. И интересная информация о количестве смитов.

maxal писал(а):

Вот архив со смитами меньшими $10^7$: http://www.onlinedisk.ru/file/552065/
Количество смитов меньших $10^n$ приведены в последовательности A104170. В частности, в вышеуказанном файле ровно A104170(7)=278411 смитов.

[Nataly-Mak]

Месяц прошёл с объявления конкурса по магическим квадратам.
Результаты удручающие. Прислано только одно (!) решение.
И это решение принадлежит постоянному участнику темы maxal'у.

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

Очень надеюсь, что, по крайней мере, привлекла хоть какое-то внимание к теме. За месяц тему просмотрели более 3300 раз.

[iig]

Чего вы хотите, слово "магический" привлекает дилетантов, но когда попоймут, что тут не магия, а математика, бросают.
Для математиков слишком узкая тема и мне, например, неинтересна.

[Nataly-Mak]

Я хочу заниматься темой, и я ею занимаюсь.

То, что вам данная тема неинтересна, это ваше личное дело. Вряд ли об этом надо писать на форуме.

[Vasily]

Магическими квадратами сейчас интересуются лишь астрологи для своих околонаучных измышлений. Но они хоть за это денежки имеют, вешая лапшу на уши наивным искателям счастья. А Вам-то на кой дались эти магические квадраты? Особенно из Смитов. Ну рассмотрите еще МК из чисел Фибоначчи или биноминальных коэффициентов. Пустая какая-то затея.

[Nataly-Mak]

А вам, похоже, совсем делать нечего

[Vasily]

Мне делать есть чего - жду ответа по-существу.