2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 На доске написаны числа 1, 2, 3, …, 2017
Сообщение02.11.2017, 11:45 
Аватара пользователя


01/12/11

8634
На доске написаны числа 1, 2, 3, …, 2017.
За один ход разрешается выбрать два любых написанных числа и заменить на их сумму или неотрицательную разность.
После нескольких ходов все числа на доске оказались равными $n$.

Каковы возможные значения $n$?

 Профиль  
                  
 
 Re: На доске написаны числа 1, 2, 3, …, 2017
Сообщение02.11.2017, 13:59 
Заслуженный участник
Аватара пользователя


13/08/08
14496
Легко можно получить все единички $(1,3-2,5-4,...,2017-2016)$.
А вот одно число будет считаться? Например, $2035153$, то есть всеобщую сумму. Или надо, чтобы было по крайней мере два числа?

 Профиль  
                  
 
 Re: На доске написаны числа 1, 2, 3, …, 2017
Сообщение02.11.2017, 14:13 
Заслуженный участник
Аватара пользователя


01/08/06
3158
Уфа
Поскольку чётность суммы всех чисел — инвариант, чётное $n$ получить невозможно.

-- Чт ноя 02, 2017 16:28:43 --

Вроде бы, любое нечётное число в диапазоне от 1 до максимально возможного можно получить.
По крайней мере, нечётные от $2035153-2\times 2016$ до $2035153$ получаются легко: сначала одна разность 2017-2016, 2016-2015, ..., 2-1, а потом суммируем до победного конца. И меньше тоже получается, но строгое описание алгоритма пока ускользает.

-- Чт ноя 02, 2017 16:38:00 --

Это я в предположении, что одно число — законный конечный результат, причём к нему всегда можно прийти от нескольких равных чисел (их должно быть нечётное количество, одно оставляем, остальные пары обнуляем, затем всё складываем).

 Профиль  
                  
 
 Re: На доске написаны числа 1, 2, 3, …, 2017
Сообщение02.11.2017, 15:19 
Заслуженный участник


20/08/14
12065
Россия, Москва
worm2 в сообщении #1261577 писал(а):
Поскольку чётность суммы всех чисел — инвариант,
Простите, почему? Выберем первые два числа $1$ и $2$ и заменим их оба на разность $2-1=1$, получим начало последовательности в виде $1,1,3,4,5,6,...$ - чётность изменилась.
Аналогично можно заменить $2$ и $3$ на их сумму и получить $1,5,5,4,5,6,...$ - и тоже чётность изменилась.
Ведь в условии неявно (опять Карл неявно!) сказано что общее количество чисел при заменах не уменьшается.

 Профиль  
                  
 
 Re: На доске написаны числа 1, 2, 3, …, 2017
Сообщение02.11.2017, 15:33 
Заслуженный участник
Аватара пользователя


09/09/14
6328
gris в сообщении #1261573 писал(а):
Легко можно получить все единички
Манипулируя этими единичками можно получать любые нечётные числа до 1008. А если вначале не всё превращать в единички, то можно продвинуться намного дальше. Вопрос в том, какое нечётное число, меньшее 2035153, получить нельзя.

 Профиль  
                  
 
 Re: На доске написаны числа 1, 2, 3, …, 2017
Сообщение02.11.2017, 15:41 
Заслуженный участник
Аватара пользователя


13/08/08
14496
Dmitriy40, я так понял, что надо "заменить два числа на их сумму или модуль разности", а не "заменить их каждое на сумму или модуль разности", то есть от одной операции количество чисел уменьшается? Впрочем, это может быть параллельной задачей. Можно ещё заменять одно число на сумму, а другое на модуль разности. Ещё одна задача.
А вот попробую посмотреть в начало Нашей Эры. Как бы подобную задачу решали кто-там-занимался-математикой-в те года.
$[1,2]\to\{1,3\}$
$[1,2,3]\to\{0,1,2,3,4,6\}$
$[1,2,3,4]\to\{0,1,2,4,5,6,8,10\}$
$[1,2,3,4,5]\to\{1,3,5,7,9,11,13,15\}$

 Профиль  
                  
 
 Re: На доске написаны числа 1, 2, 3, …, 2017
Сообщение02.11.2017, 16:01 
Заслуженный участник


20/08/14
12065
Россия, Москва
gris
Согласен, можно и разделить на три задачи. Я лишь за то чтобы яснее оговаривать какой вариант решается. Как видно не все утверждения справедливы для всех вариантов.
Ну и исходная задача всё же мне кажется про $2017$ чисел, там в условии есть слова "все числа на доске", а не "осталось число". Хотя с другой стороны тогда $n$ не ограничено сверху ... Не знаю в общем что там ТС подразумевала. Неужели так прям трудно сформулровать задачу корректно?! :evil:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

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


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

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