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

[Nataly-Mak]

Задача вообще-то пустяковая.
Имеется некоторая последовательность из 13 различных чисел, например, такая:

277  719  1019  1237  1567  2503  3163   3463  10093  16363   37307  1012213  1115533

Требуется определить, можно ли выбрать из этой последовательности подпоследовательность из 9 чисел так, чтобы в ней можно было сгруппировать три различные тройки с одинаковой суммой чисел.
Написала программку для выбора подпоследовательности из 6 чисел, чтобы в ней были две тройки с одинаковой суммой. Такую последовательность программа выдала мгновенно:

277, 1019, 3163, 719, 1237, 2503

Сумма чисел в первой тройке равна сумме чисел во второй тройке.
А вот программа для выбора подпоследовательности из 9 чисел надолго "задумалась".
Конечно, у меня компьютер тихоход, но и количество комбинаций не маленькое, если не ошибаюсь, это 259.459.200 вариантов.
Кто может помочь решить задачу?

Ещё вопрос: есть ли вообще шанс найти из произвольной последовательности из 13 чисел подпоследовательность из 9 чисел, обладающую указанным свойством? Какова вероятность? Число всех вариантов я посчитала. А число благоприятных вариантов как посчитать? По-моему, оно вообще не поддаётся подсчёту. Случайная величина.
Очень давно изучала теорию вероятностей, не помню, как описывается такая ситуация.

[Xaositect]

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

259.459.200

У меня получилось 200200 - сначала выбираем 3 из 13, потом 3 из оставшихся 10, потом 3 из 7, а потом вспоминаем, что тройки можно переставлять.

По поводу вероятности. Из геометрических соображений (условие, что суммы трех заданных троек, задает 11-мерное подпространство в 13-мерном пространстве наборов), вероятность будет падать примерно пропорционально $\frac{1}{M^2}$ при увеличении $M$ - максимального из 13 чисел.

[Nataly-Mak]

Не поняла. Как это сначала выбираем? Надо перебрать все возможные сочетания по 9 чисел из 13. Разве не так?
То есть сначала считаем, сколько можно выбрать подпоследовательностей по 9 чисел из последовательности из 13 чисел, это число сочетаний из 13 по 9, у меня получается 715 вариантов.
А в каждой такой подпоследовательности надо ещё найти все перестановки, это 9! вариантов.

[Xaositect]

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

Не поняла. Как это сначала выбираем? Надо перебрать все возможные сочетания по 9 чисел из 13. Разве не так?

Ну можно и так. Сочетаний из 13 по 9 будет 715. Потом надо еще разбить их на тройки.

-- Пн мар 07, 2011 15:00:45 --

Xaositect в сообщении #420282 писал(а):

А в каждой такой подпоследовательности надо ещё найти все перестановки, это 9! вариантов.

Все перестановки находить не надо, при перестановке слагаемых сумма не меняется.
Надо разбить девятку чисел на 3 тройки.
Пусть первое число принадлежит первой тройке. Выберем еще 2 произвольно: $C_8^2 = 28$. Осталось 6 чисел. Опять, пусть первое принадлежит второй тройке. Выберем еще 2: $C_5^2 = 10$

[Nataly-Mak]

Нет, не доходит ваш способ
Вот со всеми перестановками мне понятно. Дальше буду думать.

Так сколько у вас всего вариантов получается, если исходить из 715 подпоследовательностей из 9 чисел?

[mihiv]

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

[Nataly-Mak]

Рассуждаю; поправьте, пожалуйста, где неверно.

Итак, берём последовательность из 9 чисел.
Помещаем в первую тройку одно из 9 чисел, это 9 вариантов.
Добавляем в эту тройку два произвольно выбранные из оставшихся 8 чисел, это 28 вариантов. Первая тройка сформирована.
Осталось 6 чисел. Помещаем во вторую тройку одно из оставшихся 6 чисел, это 6 вариантов. Добавляем два произвольно выбранных из оставшихся 5 чисел, это 10 вариантов.
В тетьей тройке остаются невыбранные числа.
Итого: 9*28*6*10=15120 вариатов разбиения на тройки.

Всего для 715 последовательностей: 15120*715=10.810.800

-- Пн мар 07, 2011 16:46:17 --

mihiv в сообщении #420297 писал(а):

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

Да, это верно.

[Xaositect]

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

Помещаем в первую тройку одно из 9 чисел, это 9 вариантов.

Поскольку тройки неразличимы, мы просто можем назвать первой ту тройку, где лежит первое число и эти 9 вариантов пропадут. Аналогично с 6.

-- Пн мар 07, 2011 15:49:14 --

Вот файл со списком всех комбинаций, которые надо проверить:
http://narod.ru/disk/6979323001/data.txt.html

[Nataly-Mak]

Ага, спасибо, теперь дошло.
Получается, значит, 200200 вариантов всего. Ну, это мало
Сейчас буду пробовать написать программу перебора.

На файл с комбинациями глянула, чего он такой огромадный? 5,5 Мб.
Вы комбинации все нашли? А что же сразу уж и не проверили их, по ходу дела?

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

[Nataly-Mak]

Программу написала, все имеющиеся у меня последовательности проверила.
Похоже, что шансов никаких

[Nataly-Mak]

Переформулирую задачу с другим подходом.

Найдём последовательность из 9 простых чисел, удовлетворяющую указанному свойству, другим путём (все последовательности в этой задаче должны состоять из простых чисел), например:

5 31 47 41 61 7 131 227 167

Теперь требуется найти ещё 8 последовательностей, удовлетворяющих следующим условиям:
1) в них такие же разности между соседними членами, как и в исходной последовательности;
2) первые члены всех 9 последовательностей удовлетворяют тому же свойству: их можно сгруппировать в три различные тройки с одинаковой суммой чисел во всех тройках (эта сумма не обязана быть такой же, как в исходной последовательности).

Я начала решать задачу таким способом. Нашла 3 последовательности:

71 97 113 107 127 73 197 293 233
521 547 563 557 577 523 647 743 683
1061 1087 1103 1097 1117 1063 1187 1283 1223

Дальше моя программа «намертво» встала, ничего больше не выдаёт.

Казалось бы, всё очень просто. Однако реализовать идею с ходу не получается.
Понятно, что можно найти ровно 9 последовательностей и проверить их первые члены на выполнение условия 2).
А можно найти и больше последовательностей (10, 11, 12 или 13) и среди первых членов этих последовательностей выполнить поиск нужных 9.
Далее, если с такой исходной последовательностью ничего не получилось, берём другую исходную последовательность.

Мне кажется, что решение найти можно, но не с наскоку. Нужна эффективная программа поиска последовательностей.

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

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

[Nataly-Mak]

Один из участников конкурса прислал около 70 последовательностей из 9 простых чисел, удовлетворяющих указанному условию. Однако среди первых членов этих последовательностей не удалось найти 9 таких элементов, которые удовлетворяют тому же условию.
Тогда я попросила его найти две тройки элементов с одинаковой суммой, это получается сразу, решений несколько. Третью тройку элементов я сформировала произвольно: два элемента взяла из последовательностей, а третий элемент вычислила по известной сумме трёх элементов. Понятно, что третья последовательность не состоит из простых чисел, в ней только два числа оказались простыми. Так построен первый пандиагональный квадрат 9-го порядка, состоящий почти из простых чисел (только 7 чисел не простые). Это первое приближение к искомому решению. Почти уверена, что решение существует.
Вот 9 последовательностей:

677 743 821 1091 947 1013 1283 1361 1217
953 1019 1097 1367 1223 1289 1559 1637 1493
6697153 6697219 6697297 6697567 6697423 6697489 6697759 6697837 6697693
71433997 71434063 71434141 71434411 71434267 71434333 71434603 71434681 71434537
149980997 149981063 149981141 149981411 149981267 149981333 149981603 149981681 149981537
1597 1663 1741 2011 1867 1933 2203 2281 2137
914731133 914731199 914731277 914731547 914731403 914731469 914731739 914731817 914731673
1071407009 1071407075 1071407153 1071407423 1071407279 1071407345 1071407615 1071407693 1071407549
999974333 999974399 999974477 999974747 999974603 999974669 999974939 999975017 999974873

Это полученный из них нетрадиционный пандиагональный квадрат 9-го порядка:

1493 1283 914731133 999974399 1071407153 149981333 71434411 1867 6697837
71434267 2281 6697693 1559 677 914731199 999974477 1071407345 149981411
999974669 1071407423 149981267 71434681 2137 6697759 953 743 914731277
1019 821 914731469 999974747 1071407279 149981681 71434537 2203 6697153
71434603 1597 6697219 1097 1013 914731547 999974603 1071407693 149981537
999975017 1071407549 149981603 71433997 1663 6697297 1289 1091 914731403
1367 947 914731817 999974873 1071407615 149980997 71434063 1741 6697489
71434141 1933 6697567 1223 1361 914731673 999974939 1071407009 149981063
999974333 1071407075 149981141 71434333 2011 6697423 1637 1217 914731739

Удивляет, что среди огромного количества девяток нет ни одной, удовлетворяющей нужному условию.

[svv]

Nataly-Mak писал(а):

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

Пусть Smin и Smax -- наименьшая и наибольшая возможная сумма тройки. Выделяем массив байтов N[k], где индекс k меняется от Smin до Smax включительно. Элемент N[k] будет показывать, сколько раз встретилось число k как сумма троек.

Выбираем подпоследовательность из девяти чисел. Заполняем массив N нулями (это можно сделать быстро). Далее перебираем все тройки (в пределах подпоследовательности из девяти чисел). Вычисляем сумму тройки, пусть она равна k. Увеличиваем N[k] на единицу. Если получилось 3 -- выводим на печать.

[Nataly-Mak]

svv в сообщении #421423 писал(а):

Далее перебираем все тройки (в пределах подпоследовательности из девяти чисел).

Выше уже сказали, что перебирать все тройки в подпоследовательности из 9 чисел не надо.

Я сначала искала подпоследовательности по 9 чисел из 13 чисел. Но вообще алгоритм требует искать такие подпоследовательности из гораздо более длинных последовательностей. В приведённом выше примере участник конкурса нашёл около 70 нужных последовательностей, девятки пришлось искать из последовательности, состоящей из 70 членов (первые члены найденных последовательностей).
Он писал мне, что у него были даже варианты со 163 последовательностями. Нужных девяток он так и не нашёл.

[Nataly-Mak]

Задача закрывается, квадрат найден тем же участником конкурса, даже два квадрата.
Будут опубликованы в итогах конкурса после 12 марта.
Теперь можно искать только квадраты с меньшими магическими константами, у найденных квадратов магические константы огромные. Но они всё-таки найдены! Я и не сомневалась в их существовании.