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

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

задан 2 Ноя '17 12:51

10|600 символов нужно символов осталось
1

Сумма всех чисел здесь нечётна, так как 2018 не делится на 4. Легко заметить, что сумма написанных на доске чисел всегда имеет ту же чётность, что и сумма всех чисел от 1 до 2017. Значит, если осталось n+...+n, то n нечётно.

Покажем, что для любого нечётного числа n от 1 до S=2017*2018/2, могло остаться оно одно. Простой вспомогательный факт: если были числа 1, 2, ... , m, и мы выбираем какое-то подмножество (возможно, пустое), то сумма чисел этого подмножества может принимать все целые значения от 0 до m(m+1)/2 включительно. При m=1 и при m=2 это очевидно. Пусть m >= 3. Тогда без использования m можно набрать все суммы от 0 до (m-1)m/2, а с использованием m -- все суммы от m до m(m+1)/2. Вместе это даёт всё от 0 до m(m+1)/2, без "пробелов", так как m<=(m-1)m/2 при m>=3.

Теперь пусть k <= (S-1)/2. Набираем сумму, равную k. Остальные числа в сумме дают S-k. Если k > 0, то на последнем шаге, после получения двух сумм, берём разность большего S-k и меньшего k. Получается S-2k, что пробегает все нечётные значения S-2, S-4, ... , 1. Сумма S получается тривиальным способом.

ссылка

отвечен 2 Ноя '17 17:30

@falcao, большое спасибо!

(3 Ноя '17 18:36) Аллочка Шакед
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,373
×1,113
×370
×308
×150

задан
2 Ноя '17 12:51

показан
3611 раз

обновлен
3 Ноя '17 18:36

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru