Интересная оригинальная задача для всех

Форум для обсуждения вопросов математики

Модератор: Admin

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

Интересная оригинальная задача для всех

Сообщение nataly-mak » Вс май 01, 2011 8:45 pm

Решаю сложную задачу. Задача была предложена на проводимом на форуме dxdy.ru конкурсе «Нетрадиционные пандиагональные квадраты»:
http://dxdy.ru/topic38320.html
Задача №2.
Она не решена.

У задачи уже очень богатая история. Её долго решали на указанном форуме в теме «Магические квадраты».
Одним из участников (С. Беляевым) разработан хороший алгоритм для построения пандиагональных квадратов 6-го порядка. С помощью этого алгоритма им найден наименьший пандиагональный квадрат 6-го порядка из простых чисел. По его же программе мне удалось найти несколько пандиагональных квадратов данного порядка из чисел Смита. Квадрат с самой маленькой константой показан в конкурсной задаче. Уменьшить эту константу никак не удаётся. Наименьший обычный магический квадрат 6-го порядка из чисел Смита имеет магическую константу 2472.

Я уже написала несколько программ, рассмотрела разные алгоритмы и комбинации алгоритмов. Например, синтез общей формулы пандиагонального квадрата 6-го порядка, полученной решением СЛУ, с методом С. Беляева. По этой программе мне удалось полностью проверить одну из потенциальных магических констант – 3912. Точно могу сказать, что с такой константой квадрата не существует. В общем, программа работает, но очень долго. Проверить по этой программе все потенциальные константы нереально.

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

Изложение метода С. Беляева можно посмотреть на форуме dxdy.ru в теме «Магические квадраты», а также в моей статье «Нетрадиционные пандиагональные квадраты (часть II)».

Собираюсь написать статью, посвящённую этой интересной и сложной задаче.

Если кто-нибудь заинтересовался задачей и может помочь с программной реализацией моего алгоритма, пишите мне.

_________

Небольшое вступление в теорию отклонений от комплементарности. Буду рассказывать на конкретном примере, так понятнее.

Это пандиагональный квадрат 6-го порядка с магической константой S=5964:

Код: Выделить всё

 22  2902  94  1633  202  1111
 265  634  562  391  1894  2218
 1642  1219  1678  985  319  121
 355  526  913  1966  346  1858
 2785  166  922  535  1282  274
 895  517  1795  454  1921  382


Два числа будем называть комплементарными (или взаимно-дополнительными), если они дают в сумме величину равную K=S/3. Эта величина называется константой комплементарности, а пара комплементарных чисел – комплементарной парой.
Если квадрат ассоциативный, то константа комплементарности является константой ассоциативности.

Для приведённого примера K=5964/3=1988.
Если два числа X, Y дают в сумме величину Z<>K, то говорят, что имеется отклонение от комплементарности равное Z-K.
Например, из показанного квадрата, пары (22, 1966), (355, 1633) комлементарные.
Для пары (2902, 346) имеем отклонение от комплементарности равное (2902+346)-1988=1260.

Метод С. Беляева полностью построена на этой теории отклонений от комплементарности (для краткости говорим просто отклонения).

Для того чтобы по программе С. Беляева найти квадрат, необходимо и достаточно найти полный набор комплектов отклонений. А вот это сделать очень сложно. Все решения были найдены подбором небольших порций комплектов отклонений, отвечающих определённому критерию.

Точнее даже не так. Найти полный набор комплектов отклонений можно и не так уж сложно, но он будет содержать несколько миллионов комплектов отклонений, и обработать их все по программе С. Беляева просто нереально. Так вот задача состоит в том, чтобы учесть все ограничения, все зависимости, содержащиеся в пандиагональном квадрате, и найти минимальный (но достаточный!) набор комплектов отклонений.

Покажу квадрат 6-го порядка из чисел Смита, который является и пандиагональным, и ассоциативным (то есть идеальным):

Код: Выделить всё

7195 4306 17149 23566 2362 23962
22738 9094 24538 9634 4702 7834
23089 166 9535 18022 6502 21226
4954 19678 8158 16645 26014 3091
18346 21478 16546 1642 17086 3442
2218 23818 2614 9031 21874 18985

(Автор квадрата М. Алексеев)

Магическая константа этого квадрата равна 78540, константа ассоциативности (она же константа комплементарности) равна 26180.
Лучше один раз увидеть...

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

Сообщение nataly-mak » Ср май 04, 2011 3:49 pm

Думаю, надо сказать, что наконец-то начала писать статью об этой задаче.
Никак не могу оторваться от экспериментов. Пока написано немного, но самое главное уже освещено.
http://www.natalimak1.narod.ru/pand6.htm

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

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

Сейчас пытаюсь искать другие, более эффективные алгоритмы.
Лучше один раз увидеть...