How to translate my decision logic into a proof?

Question

Mathematics

The task is as follows:
There are n numbers written in a row. It is allowed to take any initial segment of the series a1, a2, . . . , ak and rearrange its numbers in reverse order: ak, ak−1, . . . , a1. Prove that it is possible to arrange the numbers in
ascending order after applying several such operations
. I have the following idea for solving it
1. Let's find the smallest element. Let it be at position k.
2. Flip the segment a_1 .... a_k. We get a sorted array of length 1
3. Let's find the smallest element, starting from position 2. Let it be at position k.
4. Flip the segment a_2 .... a_k. We get a sorted array of length 2
3. Let's find the smallest element, starting from position 3. Let it be at position k.
4. Flip the segment a_3 .... a_k. . We get a sorted array of length 3
And so on, until we get a sorted array

But I need to prove it a mat. by induction

Answer 1

Find k - the position of the maximum element. If k < n, then take 2 steps: turn 1...k and turn 1...n. Now the maximum is exactly at the end, and the task is reduced to sorting the first n-1 numbers.

Answer 2

By induction like this:
1. Base: a row of 2 elements - either already sorted, or sorted by flipping the entire row.
2. Suppose we know how to sort a row of k elements, consider the row a_1 ... a_k a_k+1, where the first k elements are sorted. The following are three cases:

• a_k+1 is the largest a_1 ... a_k - the row is already sorted
  
• a_k+1 is less than all a_1 ... a_k - flip a_1 ... a_k, then flip the whole row back (a_k ... a_1 a_k+1)
  
• a_k+1 must go in order between some a_m and a_m+1:
  
  1. flip the whole row a_1 ... a_k+1
     
  2. flip the row a_k+1 ... a_m+1 (it will turn out: a_m+1 ... a_k a_k+1 a_m a_m-1 ... a_1)
     
  3. flip the row a_m+1 ... a_k (it will turn out: a_k ... a_m+1 a_k+1 a_m a_m-1 ... a_1) - a new element in the desired position
     
  4. flip the whole row again