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

Дано некое целое М. Найти наибольшее N такое, что числа от 1 до N могут быть поделены на M групп, причем ни в одной из групп ни одно число не может быть представлено в виде суммы других чисел этой же группы, а также все отвечающие условию распределения.

Например, если M=2, то N=7, и возможные деления:
(1 2 7)(3 4 5 6)
(1 2 4 7)(3 5 6)
число 8 уже ни в одну из групп запихнуть нельзя - оно равно либо 1+7, либо 3+5

Для M=2 и N=8 ответ тем не менее существует: (1 2 4 8) (3 5 6 7).
Для бОльших N ответ, видимо, не существует.

А вот для M=3 уже непонятно, какой ответ. Моё решение с динамикой по масками (за 3^N * (N+M)) максимум досчитывает до N=20, но ответ по-прежнему существует. Возможно, у этой задачи вообще требуется аналитическое решение...

maxdiver,
Это называется слабые числа Шура.
Тут какие-то люди их тоже считают.

Это сообщение отредактировал(а) nworm - 4.12.2008, 19:20

Интересно, спасибо.
И брутфорс у них хороший, раз до 66 досчитал. Наверно, не стоило в сторону динамики идти...