Question

Докажите по принципу математической индукции

В ряд написано n чисел. Разрешается взять любой начальный отрезок ряда a1, a2, . . . , ak и переставить его числа в обратном порядке: ak, ak−1, . . . , a1. Докажите, что возможно расставить числа в
порядке возрастания после применения нескольких таких операций

Answer 1

n=1: ряд уже упорядочен.

Пусть удалось упорядочить ряд для n=s.

Рассмотрим n=s+1.

Если максимальный элемент ряда находится на s+1-ом месте, то остается упорядочить меньшие s членов ряда - но как это сделать, уже известно.

Пусть теперь максимальный элемент ряда находится на j-ом месте, $1\leq j\leq s$. Тогда переставляем первые $j$ членов ряда, тем самым переместив максимальный элемент на 1ое место, а затем переставляем первые $s+1$ членов ряда, тем самым переместив максимальный элемент на s+1-ое место. А как поступать в таком случае, описано ранее.

Таким образом, ряд можно упорядочить и для n=s+1.

Значит, по индукции, утверждение верно $\forall\; n\in \displaistyle{\mathbb N}$.

Ч.т.д.