Конкурс: Нетрадиционные пандиагональные квадраты

[Nataly-Mak]

Конкурс начинается 12 ноября текущего года и продлится до 18.00 мск. 12 марта 2011 г.
В конкурсе могут принять участие все желающие.
Можно решить одну или несколько из предложенных задач.
Решения присылать в личный раздел.
Если найдены лучшие решения одной и той же задачи, их тоже надо присылать.

Лучшие решения будут представлены по окончании конкурса.

О магических квадратах, простых числах и числах Смита можно посмотреть в Википедии.
Вопросы по задачам можно задавать в [2], а также в ЛС.

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

Задача №1

Известен наименьший пандиагональный квадрат 6-го порядка из последовательных простых чисел.
Смотрите последовательность A073523 в OEIS.

Построить наименьшие пандиагональные квадраты из последовательных простых чисел порядков 4 и/или 5.

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

Задача № 2

Известный пандиагональный квадрат 6-го порядка из чисел Смита имеет наименьшую магическую константу 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

Авторы квадрата С. Беляев и Н. Макарова.

Доказать, что данный квадрат является наименьшим или построить пандиагональный квадрат 6-го порядка из чисел Смита с меньшей магической константой.

Задача № 3

Построенный В. Павловским пандиагональный квадрат 7-го порядка из простых чисел имеет магическую константу 1649. Этот квадрат является регулярным и построен с использованием примитивного квадрата.
Доказать, что:
а) данный квадрат является наименьшим среди регулярных пандиагональных квадратов 7-го порядка из простых чисел;
б) не существует нерегулярных пандиагональных квадратов 7-го порядка из простых чисел с меньшей магической константой.
Если а) и/или б) неверно, привести опровергающие примеры.

Примечание: о примитивных квадратах и регулярных пандиагональных квадратах см. [1].

Задача № 4

Для построения идеального квадрата 7-го порядка достаточно найти 7 последовательностей вида $a_i, a_{i+1}, a_{i+2}, a_{i+3}, a_{i+4}, a_{i+5}, a_{i+6}$, $i = 1, 8, 15, \dots, 43$, удовлетворяющих следующим условиям:

$$a_i + a_{i+6} = a_{i+1} + a_{i+5} = a_{i+2} + a_{i+4} = 2a_{i+3},$$

$$a_1 + a_{43} = a_8 + a_{36} = a_{15} + a_{29} = 2a_{22}$$

Пример идеального квадрата 7-го порядка из последовательностей (простых чисел), удовлетворяющих указанному условию:

20233 27799 30637 37123 44017 7753 13759
43093 7717 13723 19309 26863 34429 36187
25939 33493 39979 42157 6793 13687 19273
5857 12763 19237 25903 32569 39043 45949
32533 38119 45013 9649 11827 18313 25867
15619 17377 24943 32497 38083 44089 8713
38047 44053 7789 14683 21169 24007 31573

Магическая константа квадрата равна 181321. Автор квадрата Н. Макарова.

Доказать, что указанное условие является и необходимым для построения идеального квадрата 7-го порядка или привести пример, опровергающий необходимость этого условия.
Используя указанное условие или какой-либо другой алгоритм, построить идеальный квадрат 7-го порядка из чисел Смита с наименьшей магической константой.

Примечание: пандиагональный квадрат называется идеальным, если он обладает свойством ассоциативности.

Задача № 5

Известный на сегодня пандиагональный квадрат 7-го порядка из чисел Смита имеет очень большую магическую константу – 696745.
Вот этот квадрат:

 37678 778 70582 381802 202 25618 180085
381298 23962 1921 217642 382 54814 16726
180346 54418 958 16222 405058 265 39478
39982 381361 37822 2182 234382 562 454
56218 180526 58 24214 16285 418918 526
517 53842 381622 54562 2362 180022 23818
706 1858 203782 121 38074 16546 435658

Автор квадрата Н. Макарова.
Для сравнения: магические константы пандиагональных квадратов из чисел Смита порядков 4 – 6 соответственно: 14560 (наименьшая), 8318 (наименьшая), 5964.
Представленный квадрат построен с использованием примитивного квадрата.

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

Задача № 6

Не найдено ни одного пандиагонального квадрата 9-го порядка из простых чисел. Не разработан алгоритм для такого построения. Разработан алгоритм построения идеального квадрата 9-го порядка, но идеальный квадрат из простых чисел пока не найден.

Разработать алгоритм и построить пандиагональный и/или идеальный квадрат 9-го порядка из простых чисел с любой магической константой, по возможности наименьшей.

Задача № 7

В [2] приведены примеры построения пандиагональных квадратов порядков 11 и 13 из простых чисел с использованием примитивных квадратов. Используя этот алгоритм или разработав другой, построить пандиагональный квадрат 17-го порядка из простых чисел с любой, по возможности наименьшей, магической константой.


1. THE ALGEBRAIC THEORY OF DIABOLIC MAGIG SQUARES. By Barkley Rosser and R. J. Walker
http://narod.ru/disk/23700701000/Rosser1939.rar.html

Примечание: статья переведена на русский язык С. В. Беляевым. Перевод здесь: http://svb.hut.ru/DOWN/Rosser_ru.pdf

2. Тема “Магические квадраты” topic12959.html

[Nataly-Mak]

Конкурс закончился
Мне прислали всего два решения. Представлю эти решения.

Решение задачи № 4, точнее первой её части, прислал maxal:

Контрпример:

3616, 3650, 3676, 3626, 3664, 3695, 1817, 
3607, 3629, 3654, 3622, 3696, 3663, 1873, 
2174, 2266, 2220, 2031, 3835, 5578, 5640, 
3325, 6783, 5037, 3392, 1747, 1, 3459, 
1144, 1206, 2949, 4753, 4564, 4518, 4610, 
4911, 3121, 3088, 3162, 3130, 3155, 3177, 
4967, 3089, 3120, 3158, 3108, 3134, 3168

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

_____

Этот контрпример доказывает, что приведённые в задаче условия не являются необходимыми для построения идеального квадрата 7-го порядка.
К сожалению, вторая часть задачи – построение наименьшего идеального квадрата 7-го порядка из чисел Смита – не решена.

Второй участник конкурса, alexBlack, решил задачу № 6.
Он нашёл два пандиагональных квадрата 9-го порядка из простых чисел:

Квадрат № 1:

15534163 5808276703 6780601753 9818952761 4316202827 4509221681 1523004953 1233013157 67670063
1523004887 1233013091 67669997 15534307 5808276847 6780601897 9818952683 4316202749 4509221603
9818952827 4316202893 4509221747 1523004809 1233013013 67669919 15534241 5808276781 6780601831
15534433 5808276973 6780601213 9818953031 4316203097 4509221141 1523005223 1233013427 67669523
1523005157 1233013361 67669457 15534577 5808277117 6780601357 9818952953 4316203019 4509221063
9818953097 4316203163 4509221207 1523005079 1233013283 67669379 15534511 5808277051 6780601291
15534703 5808276433 6780601483 9818953301 4316202557 4509221411 1523005493 1233012887 67669793
1523005427 1233012821 67669727 15534847 5808276577 6780601627 9818953223 4316202479 4509221333
9818953367 4316202623 4509221477 1523005349 1233012743 67669649 15534781 5808276511 6780601561

Магическая константа равна 34.072.478.061.

Квадрат № 2:

 516206219 7336893583 9818953223 8818160381 4922688311 2700863647 4178480227 1253265743 993031577
4178480161 1253265677 993031511 516206363 7336893727 9818953367 8818160303 4922688233 2700863569
8818160447 4922688377 2700863713 4178480083 1253265599 993031433 516206297 7336893661 9818953301
516206489 7336893853 9818952683 8818160651 4922688581 2700863107 4178480497 1253266013 993031037
4178480431 1253265947 993030971 516206633 7336893997 9818952827 8818160573 4922688503 2700863029
8818160717 4922688647 2700863173 4178480353 1253265869 993030893 516206567 7336893931 9818952761
516206759 7336893313 9818952953 8818160921 4922688041 2700863377 4178480767 1253265473 993031307
4178480701 1253265407 993031241 516206903 7336893457 9818953097 8818160843 4922687963 2700863299
8818160987 4922688107 2700863443 4178480623 1253265329 993031163 516206837 7336893391 9818953031

Магическая константа равна 40.538.542.911.
Здесь alexBlack изложил свой алгоритм построения нетрадиционных пандиагональных квадратов 9-го порядка.

Вот и все результаты. Поскольку участников, приславших решения, всего двое, мне трудно присудить призовые места. Пусть они будут поделившие первое место
Спасибо за участие!

Не знаю, были ли неявные участники. Может быть, они теперь выскажутся?

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

[Nataly-Mak]

Отрадно отметить, что мои коллеги не прекратили решение задач с окончанием конкурса.

Например, svb продолжает решать задачу № 2 о наименьшем пандиагональном квадрате 6-го порядка из чисел Смита. У него есть уже неплохие результаты, найден пандиагональный квадрат с магической константой 5100:

2362  895  121  166 1165  391
85  706 2155  454  778  922
94  913 1255  526  634 1678
355  382  985  517  958 1903
1642 1858  319 1219   58  4
562  346  265 2218 1507  202

Смотрите статью svb об этой задаче здесь.

Я тоже немало времени потратила на решение этой задачи, написала статью о ней.
К сожалению, результаты мне не удалось получить, установила только, что для магической константы 3912 пандиагонального квадрата не существует.

Мне удалось немного продвинуться в решении задачи № 3, найден пандиагональный квадрат 7-го порядка из простых чисел с магической константой 1597:

191 89 397 409 43 157 311
379 103 101 491 17 313 193
317 241 109 163 439 47 281
223 383 227 107 541 37 79
331 337 7 139 167 563 53
83 347 389 277 127 307 67
73 97 367 11 263 173 613

Но это не окончательное решение задачи, минимальность найденного квадрата не доказана.

alexBlack продолжил решение задачи № 6, им найден также идеальный квадрат 9-го порядка из простых чисел с магической константой 24237. И хотя минимальность квадрата не доказана, это очень хороший результат. До этого не было известно ни одного идеального квадрата 9-го порядка из различных простых чисел.
Смотрите статью alexBlack. В статье приведена общая формула идеального квадрат 9-го порядка. Этой формулой автор пользовался при поиске квадрата.

5381 5189 5273 149 107 89 83 2633 5333
977 449 443 419 5003 5039 5147 5153 1607
1583 4787 3413 4877 653 1373 3089 2909 1553
2699 3863 743 4127 2027 3767 1979 2609 2423
2969 1709 3119 3389 2693 1997 2267 3677 2417
2963 2777 3407 1619 3359 1259 4643 1523 2687
3833 2477 2297 4013 4733 509 1973 599 3803
3779 233 239 347 383 4967 4943 4937 4409
53 2753 5303 5297 5279 5237 113 197 5

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

Но ещё очень много осталось нерешённых задач.
Поэтому я решила провести второй конкурс “Нетрадиционные пандиагональные квадраты”:
topic47699.html

Приглашаю всех принять участие в этом конкурсе!

[cepesh]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.