There are $n$ numbers on a line ($1$ to $n$). The $n$ numbers can be in any order. A step is defined as: If the first number in the line is $k$, then the first $k$ numbers are reversed, Prove that after a finite number of steps we always end with $1$ as the first number.
Example:
Taking $n=5$
And arranging them in a random order
$4,1,2,3,5$.
Step 1: $4$ is the first number, first $4$ numbers are reversed,
$3,2,1,4,5$.
Step 2: Again $3$ is the first number, first $3$ numbers are reversed,
$1,2,3,4,5$.
So we ended up with $1$ as the first number after exactly 2 steps, and we need to prove that we always end up with $1$ as the first number no matter what $n$ is, or how the numbers are arranged.
My approach, I used induction but I am facing difficulty in applying the induction hypothesis, any hint would help.
Let $S$ be the set of integers $k$ which occur infinitely often as the first number. By the pigeonhole principle, $S$ is nonempty, and we want to show that $S = \{1\}$.
Let $k$ be the largest number in $S$. Suppose $k > 1$. Then at some point, $k$ is the first number, and we reverse the first $k$ numbers. Because $k = \max(S)$, we may assume that from that point on, no number larger than $k$ appears as the first number. That is, from that point on we always reverse the first $\ell$ numbers, for certain $\ell \leq k$. But at this point, $k$ is on the $k$th position, so that we keep reversing the first $\ell$ numbers for certain $\ell \in S$ which are stricty less than $k$. So $k$ will remain on the $k$th position forever. This is a contradiction with the fact that $k \in S$.
Hence $k = 1$.