It is given sequence wih length of $2017$ which consists of first $2017$ positive integers in arbitrary order (every number occus exactly once). Let us consider a first term from sequence, let it be $k$. From given sequence we form a new sequence of length 2017, such that first $k$ elements of new sequence are same as first $k$ elements of original sequence, but in reverse order while other elements stay unchanged. Prove that if we continue transforming a sequence, eventually we will have sequence with first element $1$.
Problem
Source: Bosnia and Herzegovina EGMO Team Selection Test 2017
Tags: Sequence, iterations, combinatorics
Kaskade
19.09.2018 22:32
We will use induction. Let $P\left(n\right)$ be the statement for the first $n$ numbers. For a sequence of length $1$ it is trivial.
Suppose $P\left(n\right)$ is true. Consider a sequence of length $n+1$
Observe that if the number $n+1$ is in the $n+1$ position, then it will never be affected by any reversals. So if the number $n+1$ is in the $n+1$ position, the problem is equivalent to $P\left(n\right)$.
Suppose then that the number $x$ is in the $n+1$ position, and the number $n+1$ is somewhere else in the sequence. Then while $n+1$ is not the first term in the sequence, we can treat $n+1$ as placeholder for $x$.
As the process is repeated one of two things will happen. At some point either the number $1$ will become the first term or the number $n+1$, which was a placeholder for $x$, will become the first term and we can no longer treat it as a placeholder as it affects the sequence differently.
One of these must happen because if $n+1$ never became the first term, it would be as if we had a sequence of length $n$ so by the inductive hypothesis the number $1$ must become the first term eventually.
If the number $1$ becomes the first term we are done.
If the number $n+1$ becomes the first term, we can no longer treat it as a placeholder for $x$. But now the entire sequence will be reversed and $n+1$ will go to the $n+1$ position and so as discussed the problem reduces to $P\left(n\right)$.
Hence by induction the statement is true for all $n$ and so the problem statement is just the case $n=2017$