Имя: Пароль:
IT
 
Числа по кругу
0 Ненавижу 1С
 
гуру
17.07.13
11:15
По кругу расставлены числа 1, 2, ..., N.
За один ход можно взять два любых соседних числа и заменить их на их среднее арифметическое.
При каких N>1 за конечное число ходов можно добиться равенства всех чисел?
1 Wobland
 
17.07.13
11:16
вариант раз: н=1
вариант два: н=2
2 Wobland
 
17.07.13
11:16
(1) вариант раз не проходит по условиям. а второй подходит. приз в студию!
3 Ненавижу 1С
 
гуру
17.07.13
11:17
(1) N>1
N=2 - слишком очевидно, впрочем как и 3 и 4
4 Любопытная
 
17.07.13
11:17
(1) Вариант раз не отвечает условиям задачи
5 Wobland
 
17.07.13
11:19
(3) (4) ладно, ладно. но второй отвечает. а то, что Ненавижу 1С неинтересно сформулировал - изъян Ненавижу 1С
6 Ненавижу 1С
 
гуру
17.07.13
11:23
(5) я ВСЕГДА пишу при каких, подразумевая поиск ВСЕХ, пора привыкнуть
7 Wobland
 
17.07.13
11:24
(6) я слишком мало тебя читаю, уж извини
8 Ненавижу 1С
 
гуру
17.07.13
11:34
интересен случай N=5 и N=8
9 Xapac
 
17.07.13
11:43
(8) графически пожалуйста.
10 Ненавижу 1С
 
гуру
17.07.13
11:44
() что графически?
11 acsent
 
17.07.13
11:47
может по индукции нужно попробовать. Есть N одинковых чисел, добавили еще одно. Как выровнять
12 Salimbek
 
17.07.13
12:14
(11) Не, по индукции не пойдет... Не получится у тебя "N одинаковых чисел и еще одно" на наборе N+1
13 Fenrik
 
17.07.13
12:16
Подозреваю, при N>4 не решается. Осталось найти доказательство.
14 RomanYS
 
17.07.13
13:08
(13) я тоже к этому склоняюсь
Приблизительный ход доказательства: делим круг на 2 равные части: с одной стороны большие, с другой - маленькие. Далее доказывать, что через границу нельзя протащить сумму достаточную, чтобы выровнять две половинки
15 Ненавижу 1С
 
гуру
17.07.13
13:10
(14) осталось понять, что это за сумма
16 RomanYS
 
17.07.13
13:16
(15) для N = 2K
слева S = (K+1)K/2, справа (3K+1)K/2, разница K^2.
За один шаг через границу можно "пронести" полуразность от граничных значений.
17 Wasya
 
17.07.13
13:22
(13) Что значит не решается? За N-1 шагов у нас останется одно число. То есть все числа у нас будут равны.
18 RomanYS
 
17.07.13
13:25
(17) ты слово "соседних" в условии не пропустил?
19 Wasya
 
17.07.13
13:28
>>За один ход можно взять два любых соседних числа и заменить их на их среднее арифметическое

За один ход мы убираем два числа, а записываем одно. То есть общее количество чисел с каждым ходом уменьшается на единицу.
20 RomanYS
 
17.07.13
13:30
(19) я так понимаю возвращаются всё-таки 2 числа
21 RomanYS
 
17.07.13
13:31
(19) в твоей интерпретации задача не имеет смысла
22 Ненавижу 1С
 
гуру
17.07.13
13:39
(19) сам придумал?
23 Ненавижу 1С
 
гуру
17.07.13
13:40
количество чисел ПОСТОЯННО
24 Жан Пердежон
 
17.07.13
13:53
[2;4]
других нет, инфа 100%
25 Wasya
 
17.07.13
14:03
(22) Так поянл условия задачи. Имею право.
26 Fenrik
 
17.07.13
14:27
(24) С тройкой что не так?
27 Salimbek
 
18.07.13
12:04
(26) Угу, 2,3 и 4. При бОльших числах система вырождается в две монотонно возрастающие последовательности, у которой правилами из (0) избыток от Большего числа невозможно полностью передать меньшему числу.
28 Salimbek
 
18.07.13
12:04
+(27) Разумеется это не "строго математическое доказательство"
29 Wasya
 
18.07.13
12:10
Рассмотрим последовательность чисел.
A B C, где A<=B;B<=C;A<C.
Легко убедиться, что при любом  количестве операций усреднения, соотношение A<C остается в силе.
30 Laerys
 
18.07.13
16:55
(29) чушь какая,
А стоит рядом с С, то первое же усреднение дает А=С
31 Salimbek
 
18.07.13
17:01
(30) Угу, поэтому решения задачи из (0) и возможны, но при N>4 ветки становятся параллельными и монотонными, типа 2,3,4,4,3,2 и в такой системе усреднение невозможно
32 Laerys
 
18.07.13
17:16
Все числа должны быть одинаковыми, и их сумма должно соответствовать изначальной сумме чисел, т.е. сумма равна (1+N)/2*N, значит если все числа одинаковые они равны (1+N)/2
Т.к. последовательность состоит из натуральных чисел дробная часть усредненной серии должна быть равна или 0 или 0,5. из этого следует, что каждое число не должно претерпевать более одного усреднения, получается достаточно найти минимально возможное число чисел, при котором нарушается правило одного усреднения.
Вот, как пример, доказательство более менее строгое
33 Laerys
 
18.07.13
17:19
(32) Не, не прокатит...
34 Laerys
 
18.07.13
17:28
Писать надоело, кароче доказуемо)
35 Wasya
 
19.07.13
09:55
(29) Забыл добавить. Операция усреднения между A и C запрещена. То есть рассматриваем числа не по кругу, а как обычную последовательность чисел.

Это утверждение модно обощить. Пусть есть последовательность A(1),A(2),...A(k). Операция усреднения (A(1)+A(k))/2 запрещена. A(i)<=A(i+1). A(1)<A(k). Такуб последовательность усреднить нельзя.

(31) Я к этому и клоню. Последовательность вида 2,3,4,4,3,2 усреднить нельзя. Рассмотрим двойку в первой позиции и четверку в третьй позиции. Между ними есть два пути:
2,3,4
4,4,3,2,2
Оба эти пути попадают под обощение утверждения в (29).

Осталось доказать, что для N>4 получение "монотонной" последовательности неизбежно.
36 Wasya
 
19.07.13
10:02
Информация для размышления: N=6
Из последовательности 1,2,3,4,5,6 всего за один шаг можно получить неусредняемые последовательности:
1,2,3,4,5.5,5.5
3.5,2,3,4,5,3.5
37 Ненавижу 1С
 
гуру
22.07.13
08:30
Будем обозначать число:
М - малым, если оно меньше среднего арифметического
Б - большим, если оно больше среднего арифметического
С - средним, если оно равно среднему арифметическому
Первоначальная конфигурация:
ММ...ММББ...ББ - для четных N
ММ...ММСББ...ББ - для нечетных N

Мы будем доказывать, что после очередного хода возможна только конфигурация вида:
ММ...ММ*ББ...ББ*
где звездочкой (*) обозначена последовательность из С-чисел, количеством от 0 до 2.

Первоначальная конфигурация удовлетворяет этому виду. Рассмотрим какие изменения могут произойти после очередного хода:
ММ -> ММ
ББ -> ББ
МБ или БМ -> ММ, ББ, СС
МС или СМ -> ММ
БС или СБ -> ББ
СС -> СС
Таким образом области ММ...ММ, ББ...ББ остаются "непрерывными", а "границы" из чисел С не могут превышать длину 2. То есть всего не может быть больше 2*2=4 чисел С ч.т.д.
Для N>4 "усреднить" все числа нельзя
38 Wasya
 
22.07.13
12:11
(37) Убедительно.