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

[Sonic86]

Пусть дан набор из $n$ натуральных чисел $a_j$. На каждом шаге можно выбрать произвольную пару $(a_i; a_j)$ и заменить ее парой $(\frac{a_i+a_j}{2};\frac{a_i+a_j}{2})$. Можно ли как-то просто определить, возможно ли за конечное число шагов привести данный набор к набору, состоящему из одинаковых чисел.

(у меня такое подозрение, что это уже было. Если кто помнит, дайте ссылку)

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

Для $n=2$ можно (за один шаг ), для $n=3$ уже нельзя.

Пусть дан набор $(0,0,1)$. После конечного числа указанных Вами преобразований всегда можно получить лишь набор вида $(a_1/2^{n_1}, a_2/2^{n_2}, a_3/2^{n_3})$ с целыми $a_1,a_2,a_3,n_1,n_2,n_3$. Однако набор $(1/3,1/3,1/3)$ в таком виде не представим.

-- Чт дек 10, 2009 16:42:26 --

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

[ИСН]

Или вопрос в том, какие из наборов с плохим n всё-таки можно привести? К примеру, (0,1,-1) можно...

[Sonic86]

Профессор Снэйп
Да, это я тоже нашел
Для набора $(a_1,a_2,a_3)$ если $2a_2=a_1+a_3$, то за 1 шаг приходим к решению, в противном случае не приходим вообще.
При $n=5$ очень много случаев, когда решение есть.
И еще: если набор получилось свести к набору из $n_1$ четных одинаковых и $n_2$ нечетных одинаковых чисел ($n=n_1+n_2$), то решений нету.

-- Чт дек 10, 2009 14:53:43 --

ИСН писал(а):

Или вопрос в том, какие из наборов с плохим n всё-таки можно привести? К примеру, (0,1,-1) можно...

Да, дан конкретный произвольный набор и для него надо выяснить - приводим он или нет

[gris]

можно использовать то, что среднее всех арифметическое всех чисел при каждом шаге не изменяется.

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

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

И еще: если набор получилось свести к набору из $n_1$ четных одинаковых и $n_2$ нечетных одинаковых чисел ($n=n_1+n_2$), то решений нету.

При $n=2$ (а также любой другой степени двойки) это, очевидно, не так.

-- Чт дек 10, 2009 17:05:02 --

gris в сообщении #269867 писал(а):

можно использовать то, что среднее всех арифметическое всех чисел при каждом шаге не изменяется.

Можно выразиться проще: не изменяется сумма всех чисел.

-- Чт дек 10, 2009 17:08:16 --

ИСН в сообщении #269860 писал(а):

К примеру, (0,1,-1) можно...

По условию исходный набор состоит из натуральных чисел

[Sonic86]

Профессор Снэйп писал(а):

При $n=2$ (а также любой другой степени двойки) это, очевидно, не так.

упс..., ладно, это пока эмпирическая гипотеза.

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

Пусть $n = k \cdot 2^m$, где $k$ --- нечётное число. Если сумма всех чисел набора не делится на $k$, то нельзя.

[Sonic86]

Профессор Снэйп писал(а):

По условию исходный набор состоит из натуральных чисел

Это, кстати, несущественно. Набор $a_j$ приводим $\Leftrightarrow$ набор $ka_j+b$ приводим, так что можно сразу в $\mathbb{Q}$ вылазить...
Просто на натуральных легче перебор делать и проверять неприводимость набора.

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

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

Это, кстати, несущественно.

Понятно, что несущественно. Я так, слегка подковырнул

[Sonic86]

Профессор Снэйп писал(а):

Пусть $n=k \cdot 2^m$, где $k$ --- нечётное число. Если сумма всех чисел набора не делится на $k$, то нельзя.

$(0;0;0;5;5)$ неприводим, так что это только в одну сторону, вот что плохо.

[ИСН]

Ага, похоже, в нечётном наборе одно из чисел обязано сразу равняться среднему, иначе никак.
Upd. А ни фига. (1 1 2 4 7) приводится.
- - -
Повернём другим боком. Из набора одинаковых чисел, прикладывая операцию разусреднения, к каким наборам можно придти?

[Sonic86]

ИСН
тут у меня тоже ничего не получилось. Пробовал матричное умножение использовать - тоже не получилось. Определитель матрицы - нуль, так что операция разусреднения достаточно неопределенна.

[ИСН]

Ясен хрен неопределенна: мы же каждый раз выбираем от балды, на сколько разусреднять. Зато! Зато её можно применять только ограниченное число раз, а именно, пока не кончатся одинаковые...
(я не вижу красивого финала, просто думаю туда-сюда)

[PAV]

Некоторые соображения (наверное, банальные).

Изначально разделим все на сумму чисел - имеем набор рациональных с суммой 1. Пусть они все неотрицательные. В конце должны получить для всех значение $\frac{1}{n}$. Приведем их все к одному знаменателю $M$: $(\frac{a_1}{M},\ldots,\frac{a_n}{M})$. На каждом шаге новые числа либо будут иметь тот же знаменатель $M$, либо $2M$; в последнем случае можно все оставшиеся тоже представить в виде со знаменателем $2M$. Правда, возможен случай, когда в процессе преобразования все дроби оказываются сократимыми на одно и то же число, тогда можно провести сокращение и дальше работать с меньшим знаменателем...