Задача 30752

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

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

Условие

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

Решение

Для любого набора из n чисел на доске рассмотрим следующую величину X: сумму всех чисел, уменьшенную на n. Нетрудно проверить, что это – инвариант. В наборе из условия  X = (1 + 2 + ... + 20) – 20 = 190.  После 19 операций, когда на доске останется одно число p,  X = p – 1.  Значит,  p = 191.

Ответ

191.

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

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	12
Название	Инвариант
Тема	Инварианты
задача
Номер	003