Задача 109672

Темы:    [ Процессы и операции ] [ Теория алгоритмов (прочее) ] [ Полуинварианты ]

Сложность: 5- Классы: 9,10,11

Условие

Автор: Малинникова Е.

С числом разрешается проводить одно из двух действий: возводить в квадрат или прибавлять единицу. Даны числа 19 и 98 . Можно ли из них за одно и то же количество действий получить равные числа?

Решение

Допустим, что можно, и рассмотрим способ добиться этого за наименьшее количество действий. Пусть a_k , b_k – числа, получавшиеся из 19 и 98 после k -го действия, s – число действий.
Тогда a_s=b_s=m и a_s-1 b_s-1 (так как мы рассматриваем оптимальный способ).

Действия, проведенные над a_s-1 и b_s-1 , различны. Значит, m=n² и на (s-1) -м шаге мы имели числа a_s-1=n и b_s-1=n²-1 (или наоборот; на дальнейшее решение это не влияет). Общее количество s действий не больше, чем n-18 , так как на s-1 шаге мы получили n , а каждый шаг увеличивает числа по крайней мере на 1. Тогда n²-1 могло получиться только последовательным прибавлением единиц, так как от ближайшего квадрата (n-1)² до n²-1 будет 2n-2 единицы. Следовательно, b₁>(n-1)² , поэтому все числа b₁,..,b_s-1 не являются полными квадратами.
Поэтому b_s 100 , с другой стороны a_s=a_s-1² 19² . Противоречие.

Ответ

Нельзя.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1998
Этап
Вариант	5
Класс
Класс	10
задача
Номер	98.5.10.5