Переборная задача, есть ли шанс?

[Deggial]

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

m+n=K.

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

(S=4K).

замечание за неоформление формул $\TeX$ом. В случае неоформления формул тема будет перемещена в Карантин.

[Nataly-Mak]

Надо оформить формулы сейчас? И как же это сделать, если возможность правки сообщения давно отключена?

Хорошо, оформляю:

$m+n=K$

$S=4K$

[Nataly-Mak]

Уважаемы форумчане!
Подскажите, пожалуйста, как решить такую переборную задачу.

Имеется 4 группы пар простых чисел, в каждой группе сумма всех пар чисел одинакова.
Сразу пример:

7  11  13  17  31  41  43  47  53  61  67  73  83  97  101  113  127  131  151  157  167  173  193  197  211  223  227  241  251  257  263  271  277  281  283  293  307  311  313  317

3  19  31  37  61  67  79  97  103  109  151  157  163  181  193  199  223  229  241  257

7  37  43  61  67  97  103  151  163  181  193  211  223  271  277  307  313  331  337  367

11  13  17  19  29  31  37  43  47  53  59  61  71  73  79  83  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199

Сумма пар чисел в первой группе равна 324 (7+317, 11+313 и т.д.), во второй группе - 260, в третьей группе - 374 и в четвёртой группе - 210.

Таких наборов из 4 групп может быть несколько, скажем, 100 наборов.
Требуется проверить каждый такой набор на возможность выбрать из него 4 набора из 8 непересекающихся пар чисел. То есть из каждой группы надо выбрать один набор из 8 пар чисел, при этом числа во всех выбранных парах должны быть различные.

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

7,317
283,41
307,17
47,277
317,7
131,193
61,263
311,13

Здесь мы видим повторение пары чисел 7,317 (порядок чисел в паре значения не имеет), что уже недопустимо.

Из второй группы выбраны следующие 8 пар чисел:

3,257
193,67
229,31
31,229
241,19
79,181
97,163
163,97

Здесь вообще очень много повторяющихся чисел и внутри этих 8 пар и с числами первого набора из 8 пар. Таким образом, данная выборка никуда не годится. То, что выбрано из 3-ей и 4-ой группы, не показываю, там тоже много одинаковых чисел. Достаточно уже того, что первые два набора по 8 пар выбраны неправильно, дальше смотреть нет никакого смысла.

Если не всё понятно описала, пожалуйста, задавайте ваши вопросы.
Я что-то не могу сообразить, как рационально организовать выборку таких непересекающихся пар из заданных 4-х групп чисел. А мне надо проверить много таких наборов из 4-х групп.

[Nataly-Mak]

Действительно: есть ли шанс найти нужные мне 4 группы чисел

Пока действую вручную...
Вот нашла двае группы чисел:

Группа 1

11  19  23  31  37  41  47  53  61  67  71  73  83  89  103  107  109  113  127  137  139  149  151  157  163  179  181  191  193  197  223  227  229  239  241  257  263  269  271  281  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379  383  389  397  401  409

Группа 2

3  7  19  37  43  61  73  97  103  127  139  157  163  181  193  197

Из этих групп очень просто выбрать по 8 пар чисел так, что в обоих наборах пар все числа будут различные. Это очевидно без всяких программ.
Во второй группе всего 8 пар чисел, поэтому тут и выбирать нечего: берём эти 8 пар полностью.
Далее надо выбрать из первой группа 8 пар, чтобы ни одно число в этом наборе не повторило ни одно число первого набора из 8 пар.
Например, такие 8 пар чисел выбираем из второй группы:

(11,409) (23,397) (31,389) (41,379) (47,373) (53,367) (67,353) (71,349)

Всё, две выборки есть вполне годные.
Теперь надо найти ещё две группы чисел, из которых можно выбрать ещё два набора по 8 пар со всеми различными числами (как внутри каждого набора из 8 пар, так и по отношению к числам во всех других наборах).

[whitefox]

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

Уважаемы форумчане!
Подскажите, пожалуйста, как решить такую переборную задачу.

Имеется 4 группы пар простых чисел, в каждой группе сумма всех пар чисел одинакова.

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

Сумма пар чисел в первой группе равна 324 (7+317, 11+313 и т.д.), во второй группе - 260, в третьей группе - 374 и в четвёртой группе - 210.

Таких наборов из 4 групп может быть несколько, скажем, 100 наборов.
Требуется проверить каждый такой набор на возможность выбрать из него 4 набора из 8 непересекающихся пар чисел. То есть из каждой группы надо выбрать один набор из 8 пар чисел, при этом числа во всех выбранных парах должны быть различные.

Каждый массив делим на два подмассива -- подмассив младших членов комплементарных пар и подмассив старших членов.

Для второго массива младший подмассив (3 19 31 37 61 67 79 97 103 109) имеет 10 элементов. Из них можно выбрать 8 элементов 45 способами. Переберём все эти способы, и для каждого выполним:

• исключим из остальных массивов выбранные 8 чисел и 8 комплементарных к ним;
• если число исключено из младшего подмассива, то комплементарное (для данного массива) число исключим из старшего подмассива, и наоборот;
• теперь выберем массив с наименьшим числом оставшихся элементов;
• если в младшем подмассиве меньше восьми элементов, то эта ветвь прерывается, а если больше, то перебираем все способы выбрать 8 элементов и для каждого выполняем описанное выше;
• и т.д.

[Nataly-Mak]

whitefox в сообщении #762041 писал(а):

Каждый массив делим на два подмассива -- подмассив младших членов комплементарных пар и подмассив старших членов.

Для второго массива младший подмассив (3 19 31 37 61 67 79 97 103 109) имеет 10 элементов. Из них можно выбрать 8 элементов 45 способами. Переберём все эти способы, и для каждого выполним:

• исключим из остальных трёх массивов выбранные 8 чисел и 8 комплементарных к ним;
• если число исключено из младшего подмассива, то комплементарное (для данного массива) число исключим из старшего подмассива, и наоборот;
• теперь выберем массив с наименьшим числом оставшихся элементов;
• если в младшем подмассиве меньше восьми элементов, то эта ветвь прерывается, а если больше, то перебираем все способы выбрать 8 элементов и для каждого выполняем описанное выше;
• и т.д.

whitefox, спасибо. Пытаюсь вникнуть.
1. выберем из младшего подмассива второго массива числа (3 19 31 37 61 67 79 97) (это один из 45 возможных вариантов).
2. исключим из остальных 3-х массивов выбранные числа;
3. выберем массив с наименьшим числом оставшихся элементов;
4. если в младшем подмассиве этого массива меньше 8 элементов, то проверка для варианта (3 19 31 37 61 67 79 97) закончена.
Далее выбираем второй вариант из младшего подмассива второго массива и всё проверяем точно так же.
Правильно поняла вашу схему?

[whitefox]

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

2. исключим из остальных 3-х массивов выбранные числа;

А также исключаем из остальных массивов 8 чисел комплементарных (относительно второго массива) выбранным. При этом, если число исключается из младшего подмассива текущего массива, то из старшего подмассива исключается ещё и число комплементарное (относительно текущего массива), и наоборот.

Остальное верно.

[Nataly-Mak]

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

[cepesh]

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

[Nataly-Mak]

Задача возвращается.
Прошу помощи!

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

Буду пытаться реализовать этот алгоритм.

Честно пыталась написать программу, не получилось.
Есть 4 двумерных массива. Надо сделать выборку из этих массивов.

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

И снова застряла на этой же вспомогательной задаче.

Итак, имеем 4 двумерных массива (4 группы пар простых чисел):
первая группа (21 пара):

79,431
89,421
101,409
109,401
113,397
127,383
131,379
137,373
151,359
157,353
163,347
173,337
179,331
193,317
197,313
199,311
227,283
229,281
233,277
239,271
241,269

вторая группа (15 пар):

79,419
89,409
97,401
101,397
109,389
131,367
139,359
149,349
151,347
167,331
181,317
191,307
227,271
229,269
241,257

третья группа (18 пар):

107,439
113,433
127,419
137,409
149,397
157,389
163,383
167,379
173,373
179,367
193,353
197,349
199,347
229,317
233,313
239,307
263,283
269,277

четвёртая группа (17 пар):

79,383
83,379
89,373
103,359
109,353
113,349
131,331
149,313
151,311
179,283
181,281
191,271
193,269
199,263
211,251
223,239
229,233

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

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

 79  101  439  109  227  401  379  281 
 359  233  263  409  191  197  251  113 
 89  419  257  271  269  383  149  179 
 389  311  173  131  229  83  353  347 
 283  97  167  181  431  397  107  353 
 307  313  211  433  139  277  199  137 
 193  163  349  331  373  127  241  239 
 317  379  157  151  157  151  337  367

Всё в этом решении замечательно, кроме повторения 4-х чисел.
Вот, значит, с четырьмя одинаковыми числами выборка есть.
Интересно, а с тремя (двумя, одним) повторяющимися числами есть выборки?
Ну и наконец ВЫБОРКА БЕЗ ПОВТОРЕНИЙ, самая важная и нужная.

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

Вот так я действую вручную.
Беру из второй группы первые 8 пар:

79,419
89,409
97,401
101,397
109,389
131,367
139,359
149,349

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

127,383
137,373
157,353
163,347
173,337
179,331
193,317
197,313

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

107,439
113,433
167,379
239,307
263,283
269,277

И наконец, из четвёртой группы удалось выбрать только 5 пар:

151,311
181,281
191,271
211,251
229,233

По 8 пар в этом примере выбрать не удалось.
Но это только один вариант выборки. А их будет очень много.
Однако крутила программу построения квадрата долго и решений менее чем с 4 повторениями не найдено, с 4 повторениями найдено несколько решений.

Вручную всё просто ведь, алгоритм совершенно прозрачный А программу написать не могу

P.S. Могу расписать, какая выборка (с 4 повторяющимися числами) содержится в приведённом пандиагональном квадрате.

[Nataly-Mak]

Проделала операцию, которую давно запланировала.

Для построения наименьшего пандиагонального квадрата 8-го порядка из последовательных простых чисел используется следующий массив из 64 последовательных простых чисел:

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 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439

Этот массив даёт магическую константу $S=2016$.
Именно из чисел этого массива сформированы показанные выше 4 группы пар простых чисел (это псевдокомплементарные пары).

Поскольку без повторения чисел у меня квадрат никак не получается, я решила расширить массив простых чисел, добавив в него простые числа от 3 до 73 и от 443 до 499.
Из чисел расширенного массива сформироваличь такие 4 группы псевдокомплементарных пар:

11  499 , 19  491 , 23  487 , 31  479 , 43  467 , 47  463 , 53  457 , 61  449 , 67  443 , 71  439 , 79  431 , 89  421 , 101  409 , 109  401 , 113  397 , 127  383 , 131  379 , 137  373 , 151  359 , 157  353 , 163  347 , 173  337 , 179  331 , 193  317 , 197  313 , 199  311 , 227  283 , 229  281 , 233  277 , 239  271 , 241  269

31 пара

7  491 , 11  487 , 19  479 , 31  467 , 37  461 , 41  457 , 59  439 , 67  431 , 79  419 , 89  409 , 97  401 , 101  397 , 109  389 , 131  367 , 139  359 , 149  349 , 151  347 , 167  331 , 181  317 , 191  307 , 227  271 , 229  269 , 241  257

23 пары

47  499 , 59  487 , 67  479 , 79  467 , 83  463 , 89  457 , 97  449 , 103  443 , 107  439 , 113  433 , 127  419 , 137  409 , 149  397 , 157  389 , 163  383 , 167  379 , 173  373 , 179  367 , 193  353 , 197  349 , 199  347 , 229  317 , 233  313 , 239  307 , 263  283 , 269  277

26 пар

5  457 , 13  449 , 19  443 , 23  439 , 29  433 , 31  431 , 41  421 , 43  419 , 53  409 , 61  401 , 73  389 , 79  383 , 83  379 , 89  373 , 103  359 , 109  353 , 113  349 , 131  331 , 149  313 , 151  311 , 179  283 , 181  281 , 191  271 , 193  269 , 199  263 , 211  251 , 223  239 , 229  233 

28 пар

Обратите внимание на то, что пар в каждой группе стало больше.
Ввожу эти данные в программу построения квадрата (магическая константа та же - $S=2016$) и через 5 минут получаю готовое решение!

79 389 167 229 239 241 263 409 
7 61 443 457 191 173 251 433 
421 163 37 463 149 487 97 199 
349 419 317 31 277 131 353 139 
271 257 283 53 431 109 379 233 
307 337 211 113 491 449 19 89 
313 59 401 311 41 383 461 47 
269 331 157 359 197 43 193 467

Пандиагональный квадрат 8-го порядка из различных простых чисел с магической константой $S=2016$.
Никаких проблем с построением этого квадрата! Всего 5 минут потребовалось на его построение.
Это значит, что нужная выборка из приведённых 4-х групп пар чисел существует, может быть, даже и не одна.

Чудесно, алгоритм ещё раз проверен (он был проверен в действии ещё тогда, когда я писала статью об этом алгоритме).

[12d3]

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

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

Проверил - не существует. Есть другие наборы?

-- Пт дек 05, 2014 18:05:20 --

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

[Nataly-Mak]

12d3 в сообщении #940730 писал(а):

Проверил - не существует. Есть другие наборы?

Спасибо.
Готовых наборов нет, но программа формирования наборов есть.
Наборы формируются очень просто, как я уже сказала, это группы псевдокомплементарных пар.
Обратите внимание: суммы пар чисел в каждой группе одинаковы. В первой группе эта сумма пар чисел отклоняется от константы комплементарности на 6, во второй группе на -6, в третьей группе - на 42, в четвёртой на -42. Константа комплементарности $K=S/4$
($S$ - магическая константа квадрата).
6,-6, 42, -42 - это отклонения от комплементарности. В данном алгоритме отклонения связаны именно так: $p_1$ и $-p_1$, $p_2$ и $-p_2$.

Цитата:

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

Думаю, что правильно. Числа в квадрате совсем не обязательно должны расположиться по схеме данного алгоритма (в указанной статье эта схема изображена на рис. 27). Это своего рода шаблон из псевдокомплементарных пар чисел, который, конечно же, сильно ограничивает все варианты расстановки чисел. Зато это сильно сокращает перебор.

[Nataly-Mak]

12d3
Вот здесь несколько групп пар с отклонениями $S_2$ и $-S_2$.

(Оффтоп)

83  421 , 103  401 , 107  397 , 131  373 , 137  367 , 151  353 , 157  347 , 167  337 , 173  331 , 191  313 , 193  311 , 197  307 , 211  293 , 223  281 , 227  277 , 233  271 , 241  263 
OTKLONENIE S2= 0 KOLICHESTVO PAR D= 17 
---

89  439 , 97  431 , 107  421 , 109  419 , 127  401 , 131  397 , 139  389 , 149  379 , 179  349 , 181  347 , 191  337 , 197  331 , 211  317 , 251  277 , 257  271 ,
OTKLONENIE S2= 24 KOLICHESTVO PAR D= 15

79  401 , 83  397 , 97  383 , 101  379 , 107  373 , 113  367 , 127  353 , 131  349 , 149  331 , 163  317 , 167  313 , 173  307 , 197  283 , 199  281 , 211  269 , 223  257 , 229  251 , 239  241 
OTKLONENIE S2=-24 KOLICHESTVO PAR D= 18 
---

101  439 , 107  433 , 109  431 , 131  409 , 139  401 , 151  389 , 157  383 , 167  373 , 173  367 , 181  359 , 191  349 , 193  347 , 223  317 , 227  313 , 229  311 , 233  307 , 257  283 , 263  277 , 269  271 
OTKLONENIE S2= 36 KOLICHESTVO PAR D= 19 

79  389 , 89  379 , 101  367 , 109  359 , 131  337 , 137  331 , 151  317 , 157  311 , 191  277 , 197  271 , 199  269 , 211  257 , 227  241 , 229  239 ,
OTKLONENIE S2=-36 KOLICHESTVO PAR D= 14 
---

149  439 , 157  431 , 167  421 , 179  409 , 191  397 , 199  389 , 229  359 , 239  349 , 241  347 , 251  337 , 257  331 , 271  317 , 277  311 , 281  307 
OTKLONENIE S2= 84 KOLICHESTVO PAR D= 14 

83  337 , 89  331 , 103  317 , 107  313 , 109  311 , 113  307 , 127  293 , 137  283 , 139  281 , 149  271 , 151  269 , 157  263 , 163  257 , 179  241 , 181  239 , 191  229 , 193  227 , 197  223 
OTKLONENIE S2=-84 KOLICHESTVO PAR D= 18 
---

113  439 , 131  421 , 151  401 , 163  389 , 173  379 , 179  373 , 193  359 , 199  353 , 239  313 , 241  311 , 269  283 , 271  281 
OTKLONENIE S2= 48 KOLICHESTVO PAR D= 12 

83  373 , 89  367 , 97  359 , 103  353 , 107  349 , 109  347 , 139  317 , 149  307 , 163  293 , 173  283 , 179  277 , 193  263 , 199  257 , 223  233 , 227  229 
OTKLONENIE S2=-48 KOLICHESTVO PAR D= 15 
---

Это я выбрала группы с самым большим количеством пар. Как я уже говорила, в каждой группе должно быть не менее 8 пар.
Прибавьте сюда группы с отклонениями 6, -6 и 42, -42, приведённые в примере выше.

Теперь можно брать любые комбинации групп с отклонениями $S_2$ и $-S_2$.
Есть даже группа с отклонением $S_2=0$, это не псевдокомплементарные, а комплементарные пары чисел (то есть сумма чисел в этих парах точно равна $K$, нет никакого отклонения от комплементарности; в этом примере $K=504$).
Комплементарные пары тоже можно использовать при построении пандиагонального квадрата 8-го порядка по данному алгоритму. Только пар в этой группе здесь маловато, эта группа ведь фактически должна поделиться на две, так как в этом случае $S_2=-S_2$.

(если брать группу с нулевым отклонением, то она будет и первой группой (отклонение $S_2$) и второй группой (отклонение $-S_2$); ну и плюс ещё какие-то две группы с отклонениями $S_2$ и $-S_2$ )

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

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

[12d3]

Тут маленькая загвоздка вышла - ежели взять 4 набора псевдокомплементарных пар, предоставленных вами 3 поста назад, то смешав в кучу все эти наборы, мы получим только 63 числа, а нам надо 64. Попробовав несколько вариантов(не все варианты!) из предоставленных вами наборов в предыдущем посте, я тоже не получил 64 числа.