Набор из n чисел привести к набору из n одинаковых чисел

[Sonic86]

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

Для набора $(0;0;0;4;6)$ если выбрать пару $(4;6)$, то получим неприводимый набор $(0;0;0;5;5)$, но если выбрать пару $(0;6)$ или $(0;4)$, то получим набор, который приводим к набору $(2;2;2;2;2)$ . Все варианты преобразований порождают орграф, который не дерево, и даже не слоеный. Вполне вероятно, что для определения неприводимости нужно использовать перебор.
Для $n=5$, например, неприводимы:
$(0;0;0;0;10)$
$(0;0;0;1;9)$
$(0;0;0;3;7)$
$(0;0;0;5;5)$
$(1;1;1;1;6)$
$(0;0;0;0;15)$
$(0;0;0;5;10)$
$(0;0;5;5;5)$
$(0;1;1;1;2)$
$(1;1;1;1;1)$
$(1;1;1;2;10)$
$(1;1;1;4;8)$
$(1;1;1;6;6)$
$(2;2;2;2;7)$
Вероятнее всего, что это переборная задача.

[Профессор Снэйп]

Sonic86 в сообщении #270118 писал(а):

Для $n=5$, например, неприводимы:
$(0;0;0;0;10)$
$(0;0;0;1;9)$
$(0;0;0;3;7)$
$(0;0;0;5;5)$
$(1;1;1;1;6)$
$(0;0;0;0;15)$
$(0;0;0;5;10)$
$(0;0;5;5;5)$
$(0;1;1;1;2)$
$(1;1;1;1;1)$
$(1;1;1;2;10)$
$(1;1;1;4;8)$
$(1;1;1;6;6)$
$(2;2;2;2;7)$

Набор $(a_1,\ldots,a_n)$ приводим тогда и только тогда, когда приводим набор $(b+a_1, \ldots, b+a_n)$ и тогда и только тогда, когда приводим набор $(ba_1, \ldots, ba_n)$. Посему не ясно, зачем Вы в списке неприводимых наборов упоминаете наборы $(1,1,1,1,6)$, $(0,0,0,0,15)$, $(0,0,0,0,10)$ --- ведь их неприводимость равносильна неприводимости набора $(0,0,0,0,1)$. Аналогично $(1,1,1,6,6)$, $(0,0,0,5,5)$ и $(0,0,0,1,1)$ --- также эквивалентные в смысле неприводимости наборы.

А то, что набор $(1,1,1,1,1)$ неприводим... Ржунимагу