Question

Let $(a_1,a_2,a_3,...,a_{2011})$ be a permutation (that is a rearrangement) of the numbers 1, 2, 3, . . . , 2011. Show that there exist two numbers $j,k$ such that $1\le j<k\le 2011$ and $|a_j-j|=|a_k-k|$

• A. 2010 1005
• B. 2011 1006
• C. 2011 1005
• D. 2011 1010

Answer 1

The correct option is C 2011 1005

Observe that ${\sum }_{j=1}^{2011}(a_j-j)=0$ , since $(a_1,a_2,a_3,...,a_{2011})$ is a permutation of 1, 2, 3, . . . , 2011.
$\therefore {\sum }_{j=1}^{2011}|a_j-j|=0$ is even.
Suppose $|a_{j-j}|\ne |a_{k-k}|$ for all $j\ne k$ .
This means the collection { $|a_{j-j}|:1\le j\le 2011$ (is the same as the collection {0, 1, 2, . . . , 2010} as the maximum difference is 2011 - 1= 2010.)
$\therefore {\sum }_{j=1}^{2011}|a_j-j|$ = 1 + 2 + 3 + + 2010 = $\frac{2010\times 2011}{2}=2011\times 1005$.....which is odd.
This shows that $|a_{j-j}|=|a_{k-k}|$ for some $j\ne k.$