Swap those numbers

For discussing Olympiad Level Number Theory problems
Nayeemul Islam Swad
Posts: 22
Joined: Sat Dec 14, 2013 3:28 pm

Swap those numbers

Unread post by Nayeemul Islam Swad » Fri Apr 11, 2014 11:49 am

The numbers from $1$ to $n$ are written in a line in increasing order and at each time you are allowed to swap any two neighboring numbers. Now, is it possible to have this initial sequence of numbers after $2007$ such swappings?
Why so SERIOUS?!??!

User avatar
Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm
Location: Dhaka, Bangladesh.

Re: Swap those numbers

Unread post by Labib » Fri Apr 11, 2014 5:16 pm

The answer is No.
Why? Since we can only swap two neighboring numbers, if a number is swapped with a larger number, it has to swapped again with the same number to get the initial sequence. (Otherwise the sequence will no longer be increasing)
Thus the number of swaps needed to gain the initial sequence has to be even. Thus, we cannot get the initial sequence after $2007$ swaps.
Please Install $L^AT_EX$ fonts in your PC for better looking equations,
Learn how to write equations, and don't forget to read Forum Guide and Rules.


"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes

Post Reply