Как перевести мою логику решения в доказательство?

Question

[Viva8888]

Задача такая:
В ряд написано n чисел. Разрешается взять любой начальный отрезок ряда a1, a2, . . . , ak и переставить его числа в обратном порядке: ak, ak−1, . . . , a1. Докажите, что возможно расставить числа в
порядке возрастания после применения нескольких таких операций
У меня такая идея её решения
1. Найдем самый минимальный элемент. Пусть он находится на позиции k.
2. Переворачиваем отрезок a_1 .... a_k. Получаем отсортированный массив длины 1
3. Найдем самый минимальный элемент, начиная уже с позиции 2. Пусть он находится на позиции k.
4. Переворачиваем отрезок a_2 .... a_k. Получаем отсортированный массив длины 2
3. Найдем самый минимальный элемент, начиная уже с позиции 3. Пусть он находится на позиции k.
4. Переворачиваем отрезок a_3 .... a_k. . Получаем отсортированный массив длины 3
И так далее, пока не получим отсортированный массив

Но мне нужно доказать её мат. индукцией

Comments

[AVKor]

Разрешается взять любой начальный отрезок ряда

Переворачиваем отрезок a_2 .... a_k.

Answer 1

[Alexandroppolus]

Найти k - позицию максимального элемент. Если k < n, то сделать 2 шага: разворот 1...k и разворот 1...n. Теперь максимум точно в конце, и задача свелась к сортировке первых n-1 чисел.

Answer 2

[galaxy]

Индукцией вроде так:
1. База: ряд из 2-х элементов - либо уже отсортирован, либо сортируется переворачиванием всего ряда.
2. Пусть мы знаем как отсортировать ряд из k элементов, рассмотрим ряд a_1 ... a_k a_k+1, где первые k элементов отсортированы. Далее три случая:

• a_k+1 больше всех a_1 ... a_k - ряд уже отсортирован
  
• a_k+1 меньше всех a_1 ... a_k - переворачиваем a_1 ... a_k, затем переворачиваем обратно весь ряд (a_k ... a_1 a_k+1)
  
• a_k+1 должен идти по порядку между некоторыми a_m и a_m+1:
  
  1. переворачиваем весь ряд a_1 ... a_k+1
     
  2. переворачиваем ряд a_k+1 ... a_m+1 (получится: a_m+1 ... a_k a_k+1 a_m a_m-1 ... a_1)
     
  3. переворачиваем ряд a_m+1 ... a_k (получится: a_k ... a_m+1 a_k+1 a_m a_m-1 ... a_1) - новый элемент в нужной позиции
     
  4. переворачиваем снова весь ряд
     
  
  

Comments

[hint000]

a_k+1 должен идти по порядку между некоторыми a_m и a_m+1:

Согласен с решением, просто перефразирую операции, чтобы не было разночтений (а то с индексами можно запутаться):

• переворачиваем k+1 элементов;
  
• переворачиваем k+1-m элементов;
  
• переворачиваем k-m элементов;
  
• переворачиваем k+1 элементов.
  

[Viva8888]

Оказывается можно сортировать только начальный отрезок