Задача 88306

Темы:    [ Инварианты ] [ Индукция (прочее) ]

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

Условие

На доске написаны числа 1, 2, 3, …, 20. Разрешается стереть любые два числа a и b и заменить их суммой ab + a + b. Какое число может получиться после 19 таких операций?

Решение

Заметим что имеет место равенство ab + a + b = (a + 1)(b + 1) − 1. Подсчитаем аккуратно результат после применения двух таких операций, то есть для трех чисел a, b, c. После первой операции останутся числа (a + 1)(b + 1) − 1, с. После второй операции надо взять произведение новых чисел, увеличенных на 1, и от произведения отнять 1, т.е.
(((a + 1)(b + 1) − 1) + 1)(c + 1) − 1 = (a + 1)(b + 1)(c + 1) − 1.
Аналогично для любого количества чисел.

Ответ

21! − 1.

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

кружок
Место проведения	МЦНМО
класс
Класс	7
год
Год	2004/2005
занятие
Номер	10
Название	Инварианты
Тема	Инварианты
задача
Номер	10.2