Move letters

There are many ways of achieving a solution with 2033136 swaps. Here, I will show that it is also the minimum number of swaps that is necessary. We will work with an argument based on the number of inversions of a permutation of 1, 2, ..., 2017. The initial configuration 1, 2, ..., 2017 clearly has got 0 inversions. The final configuration has got 2016 + ... + 2 + 1 = 2033136 inversions. It is already a well known fact that a single swap increments or decrements the number of inversions by exactly one. Thus, to achieve 2033136 inversions, we need at least the same number of swaps.

It seems that one method could be to move $2017$ first, such that it reaches the leftmost position- this would take $2016$ moves.

Next we could move the $2016$ card $2015$ spaces to the left, leaving it second in the line.

Repeating this for all cards from $2017$ down to $2$ , the total number of moves is the sum of the numbers from $1$ to $2016$ .

$\sum_{r=1}^{2016}r=\frac{1}{2}\times 2016\times 2017=\boxed{2033136}$ .

Is this the optimum approach? I'll use "proof by it's-the-right-answer";)

Let's say we replace $2017$ with $n$ . The hypothesis $P(n)$ asserts that the optimal method takes $(\sum_{r=1}^{n-1} r)$ steps. $P(2)$ is obviously true. We can combine the idea of contrapositive and induction together: suppose $P(k+1)$ is false, namely there is a way to play this game in less than $(\sum_{r=1}^{n} r)$ steps. There must have been at least $k$ times when the card with $k+1$ has been swapped. Taking out all these swaps, we then effectively found a way to play the game with $k$ cards in less than $(\sum_{r=1}^{k-1} r)$ steps, implying that $P(k)$ is false. This leads to a contradiction , so $P(n)$ is indeed true for any $n\ge 2$ .

1 is at the first place , it comes to second place = 1 move | third place = 2 move | Therefore , No. Of moves = place no. - 1 | So , to acquire 2017th place , 1 will have to make 2016 moves. Similarly , to acquire 2016th place , 2 will have to make 2015 moves. | So, total no. of moves = 2016 + 2015 + 2014 +..... + 3 + 2 + 1 | Total no. Of moves = n(n+1)/2 .. Here n=2016 | 2016×2017/2 = 2033136

Let $f(n)$ be number of moves it takes to swap a whole sequence into its reverse. If we add 1 extra card, then for $n+1$ cards, first do $f(n)$ moves to reverse the 1st $n$ cards followed by moving the remaining card through the whole sequence. Thus for example, if we are considering 4 cards, $1,2,3,4$ we do $f(3)$ moves to end up with $3,2,1,4$ then swap to get succesively $3,2,4,1$ . $3,4,2,1$ and finally $4,3,2,1$ . Thus for any general n we can see that $f(n+1)=f(n)+n$

Also $f(1)=0$ as for a single card it is already reversed. So solving the above relation by just summing both sides from 1 to n we see that almost all $f$ cancel each other giving $f(n+1)=f(1)+\frac{(n)(n+1)}{2}$ Thus $f(n+1)=\frac{(n)(n+1)}{2}$ Putting $n=2016$ , we get $f(2017)=2017*1008=2033136$

From the beginning, we will swap 1 from the leftmost to the right most. It takes 2016 steps. Then we will swap 2 from the leftmost to the 2nd rightmost. It takes 2015 steps this time. And then we will swap 3 from the leftmost to the 3rd rightmost. It takes 2014 steps. ...... At last we swap 2016 from the leftmost to the 2016th leftmost. It takes 1 steps.

So overall it takes 1 + 2 + 3 + 4 + ... + 2016 = $\frac{2016(1 + 2016)}{2}$ = 2033136

Suppose you have 2 cards then Minimum number of swaps=1 Similarly for 3 cards 3 swaps For 4 cards 6 swaps Therefore for "n" number of cards total swaps required = ( n(n-1) ) / 2 Therefore For 2017 cards swaps required = (2017 × 2016)/2 = 2017 × 1008 = 2033136