Question

На доске написаны числа 1, 2, 3, …, 2017. За одну операцию разрешается стереть любые два числа a и b и записать вместо них число a+b-1. После некоторого количества таких операций на доске останется одно число. Какое?

Answer 1

На каждом шаге сумма всех написанных на доске чисел уменьшается на 1, и количество чисел уменьшается на 1.

Всего чисел 2017, их сумма равна 2017 * 2018 / 2 = 2035153, значит, потребуется 2016 шагов, и после них сумма чисел станет равной 2035153 - 2016 = 2033137. Ну а так как на доске осталось всего одно число, то оно и равно всей сумме.

Ответ. 2033137

Answer 2

Для решения этой задачи можно использовать некоторые наблюдения.

Заметим, что каждая операция уменьшает общее количество чисел на доске на 1. Поскольку в начале у нас 2017 чисел, то после 2016 операций на доске останется одно число.

Попробуем применить операцию к нескольким числам и посмотреть, как изменяется сумма чисел на доске.

Пусть у нас есть числа a, b и сумма всех чисел на доске равна S. После применения операции сумма чисел уменьшится на (a + b - 1), то есть станет равной (S - (a + b - 1)).

Если мы применим операцию к числам a и b, а затем к результату и числу c, то общая сумма чисел на доске станет равной:

(S - (a + b - 1)) - (S - (a + b - 1) + c - 1) = S - (a + b - 1) - S + (a + b - 1) - c + 1 = c.

Таким образом, сумма чисел на доске не изменится, если мы применим операцию к трем числам.

Теперь рассмотрим задачу в обратном порядке. Изначально у нас осталось одно число, и мы применили операцию к трём числам. Полученное число будет суммой этих трёх чисел минус два (так как каждое число изначально было увеличено на 1 при операции). Обозначим полученное число за N.

Так как у нас изначально было 2017 чисел, мы применили операцию 2016 раз и осталось одно число. Поэтому это число N должно быть получено путем применения операции к трем числам 2016 раз.

Так как каждая операция не меняет сумму чисел на доске, то общая сумма чисел на доске после применения операции 2016 раз будет равна сумме чисел на доске в начале. В начале на доске были числа от 1 до 2017, и их сумма равна сумме арифметической прогрессии.

Сумма арифметической прогрессии S_n = (n/2)(a_1 + a_n), где n - количество элементов в прогрессии, a_1 - первый элемент, a_n - последний элемент.

В нашем случае n = 2017, a_1 = 1, a_n = 2017, поэтому сумма чисел на доске в начале равна S = (2017/2)(1