|
|
 |
Условие
В строке записано несколько чисел. Каждую секунду робот выбирает какую-либо пару рядом стоящих чисел, в которой левое число больше правого, меняет их местами и при этом умножает оба числа на 2. Докажите, что через некоторое время сделать очередную такую операцию будет невозможно.
Решение
Пусть числа записаны на карточках, выложенных в ряд. Будем менять местами карточки и увеличивать вдвое числа на них. Докажем, что две карточки, раз поменявшись местами, “обратно” поменяться не могут. (Отсюда будет следовать, что время работы робота не превышает количества пар карточек.)
Предположим противное и выберем пару (A, B), первой поменявшуюся обратно. Ясно, что в промежутке между прямым и обратным обменами была ещё одна операция с A или B (иначе левое число так и осталось бы меньше правого). Однако карточка C, поменявшись с A, попадёт между A и B. Снова с A она не менялась (обратный обмен A и B – первый), остаться между A и B она тоже не могла – тогда A и B не смогли бы снова поменяться. Значит, C поменялась и с B. Отсюда следует, что A и B (между прямым и обратным обменами) участвовали в равном количестве обменов, поэтому числа на них увеличились в одно и то же число раз – правое осталось больше, и они не могли поменяться. Противоречие.
Замечания
8 баллов
