Это гипотеза? Над доказательством думали?
Надо всего лишь показать, что приведённый алгоритм всегда завершается успешно. Но не думал в этом направлении.
Напрасно не думали. Это очень важная гипотеза! Её желательно доказать.
Если она будет доказана, тогда построение пандиагонального квадрата будет равносильно поиску набора из 4-х попарно ортогональных покрытий.
Цитата:
Алгоритм есть, но реализовывать его не стал.
Это поиск с возвратом.
Строим четыре покрытия одновременно.
Для этого используем найденную Вами базу разбиений.
По очереди добавляем в строящиеся покрытия новые разбиения.
При этом проверяем чтобы новое разбиение не пересекалось с другими разбиениями своего покрытия, а с разбиениями других покрытий пересекалось ровно в одной точке.
Если в базе нет такого разбиения -- делаем откат.
И алгоритм поиска набора 4-х попарно ортогональных покрытий очень простой и понятный.
За чем дело стало?
-- Пт авг 30, 2013 11:04:21 --Давайте подумаем все вместе над вопросом существование/несуществования пандиагонального квадрата 7-го порядка из различных простых чисел с магической константой 733. Есть всего два массива простых из 49 чисел, которые надо подвергнуть анализу.
Массив №1:
Код:
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 233 239
Состоит из следующих вычетов по модулю 9:
вычет 0 - нет
1 - 8 шт
2 - 8 шт
3 - 1 шт
4 - 8 шт
5 - 9 шт
6 - нет
7 - 7 шт
8 - 8 шт
Попробуем проанализировать возможность построения пандиагонального квадрата 7-го порядка с магической константой
733, как это сделал в приведённом выше доказательстве
svb.
-- Пт авг 30, 2013 11:16:22 --Массив №2 для той же магической константы
733:
Код:
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 227 229 239
Состоит из следующих вычетов по модулю 9:
вычет 0 - нет
1 - 8 шт
2 - 9 шт
3 - 1 шт
4 - 9 шт
5 - 9 шт
6 - нет
7 - 6 шт
8 - 7 шт
-- Пт авг 30, 2013 11:25:10 --mertzу меня почему-то только два потока работают вместо 4
-- Пт авг 30, 2013 11:37:30 --Вот нашла, наконец, и доказательство
12d3:
Итак, очевидно приведенный набор с константой 3719 единственен. Если мы рассмотрим остатки чисел по модулю 9 в данном наборе, то увидим такое распределение остатков:
0 - 6 штук.
3 - 1 штука.
4 - 27 штук.
6 - 8 штук.
8 - 1 штука.
Остаток от нашей константы 3719 равен 2.
Теперь нам надо найти, какие наборы из 7 остатков могут давать в сумме остаток 2. Тут небольшой перебор, его можно провести ручками, можно на компьютере перебрать, я приведу сразу результат:
Код:
4 4 6 6 6 6 6
4 4 4 6 6 6 8
3 4 4 4 4 4 6
0 6 6 6 6 6 8
0 3 4 4 6 6 6
0 3 4 4 4 6 8
0 0 3 6 6 6 8
0 0 4 4 4 4 4
0 0 0 4 4 6 6
0 0 0 4 4 4 8
0 0 0 0 6 6 8
0 0 0 0 3 4 4
0 0 0 0 0 3 8
Всего получается 13 вариантов строчек.
Теперь надо выбрать 7 строчек так, чтобы суммарное кол-во остатков каждого типа в этих строчках было равно кол-ву остатков во всем наборе(указанному выше).
Я тут перебирал ручками, используя тот факт, что остатков 4 в наборе очень много. Получил всего один вариант набора из 7 строк.
4 4 6 6 6 6 6 - 2 штуки
0 0 4 4 4 4 4- 3 штуки
4 4 4 6 6 6 8- 1 штука
3 4 4 4 4 4 6 - 1 штука
(Оффтоп)
Небольшое отступление. Тут видно, что генерировать наборы из 7 строк надо, выбирая строчки из этих групп. А если делать перебор по всем строкам, это будет намного дольше. у меня сгенерировалось не менее 10000 наборов из 7 строк. Один из них:
Код:
4 22 438 483 825 861 1086
58 85 627 645 690 762 852
27 94 265 648 778 922 985
121 166 274 576 729 895 958
346 378 454 535 634 666 706
202 319 517 636 654 663 728
355 382 391 526 562 588 915
Очевидно, такое же распределение должно быть для столбцов.
У нас должно быть три строки с нулями. и три столбца с нулями. Рассмотрим клетки, которые находятся в строках без нулей, но в столбцах с нулями. В этих клетках могут быть только четверки, ибо в столбцах с нулями, кроме нулей находятся только четверки. То есть получаем, что в каждой строке без нулей находится минимум 3 четверки, что противоречит найденному распределению остатков. То есть, даже ПМК построить из данного набора нельзя.
Имеем два аналогичных доказательства для магических квадратов 7-го и 8-го порядков (для порядка 8 см. выше). Но это были обычные магические квадраты.
Теперь у нас пандиагональный квадрат 7-го порядка. Можно ли для него применить такое же доказательство?