2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 13:39 
Аватара пользователя
Для $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$ является степенью двойки.

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 13:50 
Аватара пользователя
Или вопрос в том, какие из наборов с плохим n всё-таки можно привести? К примеру, (0,1,-1) можно...

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 13:52 
Профессор Снэйп
Да, это я тоже нашел :-)
Для набора $(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) можно...

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

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 14:03 
Аватара пользователя
можно использовать то, что среднее всех арифметическое всех чисел при каждом шаге не изменяется.

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 14:04 
Аватара пользователя
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) можно...

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

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 14:09 
Профессор Снэйп писал(а):
При $n=2$ (а также любой другой степени двойки) это, очевидно, не так.

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

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 14:11 
Аватара пользователя
Пусть $n = k \cdot 2^m$, где $k$ --- нечётное число. Если сумма всех чисел набора не делится на $k$, то нельзя.

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 14:12 
Профессор Снэйп писал(а):
По условию исходный набор состоит из натуральных чисел

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

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 14:16 
Аватара пользователя
Sonic86 в сообщении #269874 писал(а):
Это, кстати, несущественно.

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

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 14:21 
Профессор Снэйп писал(а):
Пусть $n=k \cdot 2^m$, где $k$ --- нечётное число. Если сумма всех чисел набора не делится на $k$, то нельзя.

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

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

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

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

 
 
 
 Re: Набор из n чисел привести к набору из n одинаковых чисел
Сообщение10.12.2009, 15:37 
Аватара пользователя
Некоторые соображения (наверное, банальные).

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

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group