Докажите по принципу математической индукции
В ряд написано n чисел. Разрешается взять любой начальный отрезок ряда a1, a2, . . . , ak и переставить его числа в обратном порядке: ak, ak−1, . . . , a1. Докажите, что возможно расставить числа в
порядке возрастания после применения нескольких таких операций
В ряд написано n чисел. Разрешается взять любой начальный отрезок ряда a1, a2, . . . , ak и переставить его числа в обратном порядке: ak, ak−1, . . . , a1. Докажите, что возможно расставить числа в
порядке возрастания после применения нескольких таких операций
More Questions From This User See All
Answers & Comments
Verified answer
n=1: ряд уже упорядочен.
Пусть удалось упорядочить ряд для n=s.
Рассмотрим n=s+1.
Если максимальный элемент ряда находится на s+1-ом месте, то остается упорядочить меньшие s членов ряда - но как это сделать, уже известно.
Пусть теперь максимальный элемент ряда находится на j-ом месте,
. Тогда переставляем первые 
членов ряда, тем самым переместив максимальный элемент на 1ое место, а затем переставляем первые 
членов ряда, тем самым переместив максимальный элемент на s+1-ое место. А как поступать в таком случае, описано ранее.
Таким образом, ряд можно упорядочить и для n=s+1.
Значит, по индукции, утверждение верно
.
Ч.т.д.