What is the minimum number of moves required for the above cards to be arranged backwards as 2017, 2016, ..., 2, 1?

126 views

You have 2017 cards numbered 1, 2, 3, ..., 2017 in the same order. In each move, you can change the order of two adjacent cards. (For example, if you had only four cards arranged as 1234, what you could achieve in one move would be 2134, 1324, or 1243.)

What is the minimum number of moves required for the above cards to be arranged backwards as 2017, 2016, ..., 2, 1?

posted Mar 8, 2017

+1 vote

This is bubble sort problem. In first 2016 moves the sequence becomes 2,3.......2017,1
Then 2015 moves will make it 3,4....................2017,2,1
Thus the number of moves required is (2016/2)*(2*1+(2015)*1)=2033136 or
(2016/2)*(2*2016+(2015)*(-1))= 2033136

The general answer is ∑(n-1) where n is the number of cards.
This can be concluded with the help of 4 and 5 card cases.
4 card case:
1 2 3 4
2 3 4 1 ( 3 moves )
3 4 2 1 ( 2 moves )
4 3 2 1 ( 1 move )
ie., 3 + 2 + 1 = 6 = ∑(3) = 3*4/2 = 6.
Also for n = 5 we get 4 + 3 + 2 + 1 = 10 = ∑(4) = 4*5/2 = 10.
Similarly this can be generalised for any integer value of n.
So for n = 2017, the answer is going to be
∑(2016) = ((2016*2017)/2) = 20,33,136.

Similar Puzzles