Операции с числами

[TOTAL]

Dina98 в сообщении #1612701 писал(а):

Монотонность должна сохраняться:

(5,6) -> (4,6) -> (4,5) -> (4,4) -> (3,4)

Каждая позиция уменьшилась на 2.

А раньше не должна была монотонность сохраняться?

Dina98 в сообщении #1612626 писал(а):

$2n$ шагов, ошиблась.

6, 6, 6
6, 5, 5
6, 4, 4
5, 3, 4
4, 2, 4
3, 2, 3
2, 2, 2
Всего 6 шагов, все уменьшились на $2n-2 = 4$.

[Dina98]

Даны целые положительные числа $a_1 \le \ldots \le a_n$, где хотя бы одно из чисел четное.
Разность между максимальным и минимальным числом не более единицы.

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

Доказать, что после $2n$ шагов, $n \ge 2$, число в каждой позиции на $2n-2$ меньше начального числа на той же самой позиции.

-- 06.10.2023, 17:55 --

mihaild в сообщении #1612658 писал(а):

Dina98 в сообщении #1612640 писал(а):

Второе предложение в начальном тексте: разность между максимальным и минимальным числом не более единицы

Т.е. у нас по итогу сколько-то чисел равных $k$, оставшиеся равны $k + 1$?

Да (ну или все равны).

-- 06.10.2023, 17:57 --

wrest в сообщении #1612707 писал(а):

Dina98 в сообщении #1612705 писал(а):

все позиции уменьшатся на 2n-2.

Что это значит? Сумма уменьшится или каждое число?

Каждое!

[wrest]

Dina98
Я для вас написал программу на pari/gp
Она состоит из двух фукций. Первая функция step() на вход принимает вектор (массив) чисел, а на выход отдает массив после одного шага.
step(v)=my(v1=vecsort(v));v1=apply(x->x-1,v1);for(i=1,#v1,if(v1[i]%2==1,v1[i]=v1[i]+1;return(v1)))
Например, не вход даём массив [1,1,1,2] на выходе получаем массив [0,0,0,2]
? step([1,1,1,2])
%358 = [0, 0, 0, 2]
?
Функция steps1() принимеет на вход массив, количество шагов, и делает шаги, затем печатает что получилось:

(steps1())

steps2(v,n)=my(s0=vecsum(v));if(vecprod(v)%2==1 || vecmax(v)-vecmin(v)>1,print("bad vector ",v);break());print("start:",v," sum:",s0);for(i=1,n,v=vecsort(step(v)));print("finish:",v," final sum:",vecsum(v)," decrease:",s0-vecsum(v)," total steps:",n )

Например, на вход даём массив [11,11,12]и просим сделать 2 шага.
? steps1([11,11,12],2)
start:[11, 11, 12] sum:34
finish:[9, 10, 11] final sum:30 decrease:4 total steps:2
?

Функция steps2() дополнительно к тому что делает функция steps1() ещё печатает все промежуточные шаги.

(steps2())

steps2(v,n)=my(s0=vecsum(v));if(vecprod(v)%2==1 || vecmax(v)-vecmin(v)>1,print("bad vector ",v);break());print("start:",v," sum:",s0);for(i=1,n,v=vecsort(step(v));print("step ",i," ",v," sum:",vecsum(v)));print("finish:",v," final sum:",vecsum(v)," decrease:",s0-vecsum(v)," total steps:",n )

Например, на вход даём массив [11,11,12] и просим сделать 2 шага.

? steps2([11,11,12],2)
start:[11, 11, 12] sum:34
step 1 [10, 10, 12] sum:32
step 2 [9, 10, 11] sum:30
finish:[9, 10, 11] final sum:30 decrease:4 total steps:2
?

pari/gp online есть тут: https://pari.math.u-bordeaux.fr/gp.html
Вы можете "поиграться" разными входными массивами и количеством шагов, "допилить" условия до верных и запостить новые условия.

-- 06.10.2023, 17:10 --

Dina98 в сообщении #1612714 писал(а):

то числа сортируем, чтобы сохранялся неубывающий порядок.

Доказать, что после $2n$ шагов, $n \ge 2$,

А, это новое. Ортировка у меня предусмотрена была. Смотрим:
? steps2([11,11,12,12,12,12],4)
start:[11, 11, 12, 12, 12, 12] sum:70
step 1 [10, 10, 11, 11, 11, 12] sum:65
step 2 [9, 10, 10, 10, 10, 11] sum:60
step 3 [8, 9, 9, 9, 10, 10] sum:55
step 4 [8, 8, 8, 8, 9, 9] sum:50
finish:[8, 8, 8, 8, 9, 9] final sum:50 decrease:20 total steps:4
?
Видим, что два первых числа 11 уменьшились на 3, а два следующих за ними числа 12 -- уменьшились на 4, два же последних числа 12 опять уменьшились 3.

[TOTAL]

wrest в сообщении #1612721 писал(а):

А, это новое. Смотрим:
? steps2([11,11,12,12,12,12],4)
start:[11, 11, 12, 12, 12, 12] sum:70
step 1 [10, 10, 11, 11, 11, 12] sum:65
step 2 [9, 10, 10, 10, 10, 11] sum:60
step 3 [8, 9, 9, 9, 10, 10] sum:55
step 4 [8, 8, 8, 8, 9, 9] sum:50
finish:[8, 8, 8, 8, 9, 9] final sum:50 decrease:20 total steps:4
?
Видим, что два первых числа 11 уменьшились на 3, а два следующих за ними числа 12 -- уменьшились на 4, два же последних числа 12 опять уменьшились 3.

Шагов надо было $12$ делать (условие такое)

[Dina98]

Но это только 4 шага! Надо 6*2=12.

[wrest]

TOTAL в сообщении #1612725 писал(а):

Шагов надо было $12$ делать (условие такое)

Dina98 в сообщении #1612726 писал(а):

Но это только 4 шага! Надо 6*2=12.

А.... это условие я просмотрел!

Ну теперь всё верно. Чтобы программа не пропала, добавил ещё функцию steps3() которая только печатает сколько нужно шагов.

(Оффтоп)

steps3(v)=if(vecprod(v)%2==1 || vecmax(v)-vecmin(v)>1,print("bad vector ",v);break());print("start: ",v);for(i=1,#v*2,v=vecsort(step(v));print("step ",i," ",v));

? steps3([11,11,11,12])
start: [11, 11, 11, 12]
step 1 [10, 10, 10, 12]
step 2 [9, 9, 10, 11]
step 3 [8, 8, 10, 10]
step 4 [7, 8, 9, 9]
step 5 [6, 8, 8, 8]
step 6 [6, 7, 7, 7]
step 7 [6, 6, 6, 6]
step 8 [5, 5, 5, 6]
?

[del]

[TOTAL]

Числа представляют собой килограммовые шарики на высоте $a_i$ метров.

1) За 2 шага количество четных и нечетных чисел не меняется.
2) За все шаги центр тяжести опустился на целое (четное!) число метров.
3) Шарики не могут расползтись более чем на 3 слоя по высоте.

Из (3) и (1) следует, что все чётные (или все нечетные) так и остались на одном слое.
Тогда из (2) следует, что и все нечётные (или все четные) остались на одном слое.