Как решить задачу по комбинаторике?

Question

[Дмитрий Смеркс]

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

Comments

[Lander]

Думаю тут можно более логически решить. Разбейте числа на группы близкие по значению. Тогда скорее всего числа из одной группы будут располагаться на диагоналях и окружностях. А там уже можно либо немножечко "поиграться" с их перестановкой и по-подбирать уточняющее решение.

Answer 1

[Rsa97]

Представляете кружки с числами как элементы массива [0..18]. Можете подписать их на рисунке, чтобы ничего не перепутать. При этом для простоты номера 0, 1 и 2 можно присвоить кружкам с зафиксированными числами.
Составляете 12 формул - сумм по кругам и радиусам, вида
x[0] + x[3] + x[4] + x[5] + x[6] + x[7]
x[1] + x[2] + x[8] + x[9] + x[10] + x[11]
и т.д.
Затем рекурсивно подставляете в массив [3..18] комбинации по 16 чисел из оставшихся 17, вычисляете все суммы и проверяете их на равенство.

Comments

[Дмитрий Смеркс]

Я немного не понял, куда формулы занести?

[Rsa97]

Дмитрий Смеркс, В программу

[Aves]

3,5*10^14 вариантов будет довольно долго проверять

[Rsa97]

Aves, Ускорить то можно, но это уже не будет чистой комбинаторикой. Для этого надо отсеивать варианты как можно раньше.
Скажем, если выбросить из набора (1, ..., 20) два числа (одно пропущенное и одно в центральном кружке, то сумма оставшихся должна делиться на 3. Записав три из оставшихся чисел в кружки средней окружности сразу получаем ещё одно число. Так можно построить алгоритм решения конкретно под эту задачу.

[Дмитрий Смеркс]

Нет, не в этом смысле)))
Я всё понял, достаточно интересная идея, но проблема в том, что каким образом, вы формулы составляете? И по ним считается сумма первая и вторая, а потом сравнивается? И пожалуй главное - как сделать, чтобы комбинации не повторялись? Не шли 1 11111 1222222 и т.д. Извиняюсь, конечно, возможно глупые вопросы, но буквально немного не дохожу до решения

[Rsa97]

Дмитрий Смеркс, Так я же написал. Нумеруете кружки и составляете суммы по окружностям и радиусам.
Генерировать перестановки лучше лексикографически.