Задача 35225

Тема:    [ Инварианты ]

Сложность: 3+ Классы: 8,9,10

Условие

На доске выписаны числа 1, ½, ..., ¹/_n. Разрешается стереть любые два числа a и b и заменить их на число  ab + a + b.
Какое число останется после  n – 1  такой операции?

Подсказка

При этой операции сохраняется произведение чисел, увеличенных на 1.

Решение

Пусть в некоторый момент на доске написаны числа a, b, ... , z. Рассмотрим произведение  P = (a + 1)(b + 1)...(z + 1).  После замены пары чисел a, b на  ab + a + b  в указанном произведении  (a + 1)(b + 1) заменится на  ab + a + b + 1 = (a + 1)(b + 1).  Таким образом, операция величину P не меняет. Отсюда следует, что число, которое остаётся в конце, не зависит от порядка выполнения операций и равно
(1 + 1)(½ + 1)...(¹/_n + 1) – 1 = ²/₁·³/₂·...·ⁿ⁺¹/_n – 1 = (n + 1) – 1 = n.

Ответ

n.

Источники и прецеденты использования

web-сайт

задача