2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Операции с числами
Сообщение06.10.2023, 16:43 
Заслуженный участник
Аватара пользователя


23/08/07
5501
Нов-ск
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$.

 Профиль  
                  
 
 Re: Операции с числами
Сообщение06.10.2023, 16:53 


03/10/16
18
Даны целые положительные числа $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.

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


Каждое!

 Профиль  
                  
 
 Re: Операции с числами
Сообщение06.10.2023, 17:01 


05/09/16
12203
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. :mrgreen:

 Профиль  
                  
 
 Re: Операции с числами
Сообщение06.10.2023, 17:17 
Заслуженный участник
Аватара пользователя


23/08/07
5501
Нов-ск
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. :mrgreen:
Шагов надо было $12$ делать (условие такое)

 Профиль  
                  
 
 Re: Операции с числами
Сообщение06.10.2023, 17:18 


03/10/16
18
Но это только 4 шага! Надо 6*2=12.

 Профиль  
                  
 
 Re: Операции с числами
Сообщение06.10.2023, 17:18 


05/09/16
12203
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]

 Профиль  
                  
 
 Re: Операции с числами
Сообщение06.10.2023, 18:23 
Заслуженный участник
Аватара пользователя


23/08/07
5501
Нов-ск
Числа представляют собой килограммовые шарики на высоте $a_i$ метров.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group