Maths Olympiad Prep

Library / /44 of 69

Combinatorics Difficulty 6.3 National olympiad Prove it Mongolia

Let Iσ={σii:iI}I_{\sigma} = \{ |\sigma_i - i| : i \in I \} be sets formed by every permutation σ=(σ1,σ2,,σ2014)\sigma = (\sigma_1, \sigma_2, \dots, \sigma_{2014}) of the set I={1,2,,2014}I = \{1, 2, \dots, 2014\}. Find all possible values of Iσ|I_{\sigma}|.

Solution

If σ={2014,2013,,1008,1,1007,1006,,2}\sigma = \{2014, 2013, \dots, 1008, 1, 1007, 1006, \dots, 2\} then Iσ=2013|I_\sigma| = 2013.
If σ={2013,2012,,1008,1007,1,1006,1005,,2,2014}\sigma = \{2013, 2012, \dots, 1008, 1007, 1, 1006, 1005, \dots, 2, 2014\} then Iσ=2012|I_\sigma| = 2012.
If σ={2k,2k1,,k+1,1,k,k1,,2,2k+1,2k+2,,2014}\sigma = \{2k, 2k-1, \dots, k+1, 1, k, k-1, \dots, 2, 2k+1, 2k+2, \dots, 2014\} then Iσ=2k1|I_\sigma| = 2k-1; k=1,,1007k = 1, \dots, 1007.
If σ={2k+1,2k,,k+2,1,k+1,k,,2,2k+2,2k+3,,2014}\sigma = \{2k+1, 2k, \dots, k+2, 1, k+1, k, \dots, 2, 2k+2, 2k+3, \dots, 2014\} then Iσ=2k|I_\sigma| = 2k, k=1,,1006k = 1, \dots, 1006.
If σ={1,2,,2014}\sigma = \{1, 2, \dots, 2014\} then Iσ=1|I_\sigma| = 1.
In other words, Iσ|I_\sigma| takes values 1,2,,20131, 2, \dots, 2013.

Now let's prove that Iσ2014|I_\sigma| \neq 2014. If Iσ=2014|I_\sigma| = 2014 then Iσ={0,1,2,,2013}I_\sigma = \{0, 1, 2, \dots, 2013\}. Since Iσ={σii:iI}I_\sigma = \{|\sigma_i - i|: i \in I\}, we get iI(σii)=0\sum_{i \in I} (\sigma_i - i) = 0. On the other hand, among the numbers ±0,±1,±2,,±2013\pm 0, \pm 1, \pm 2, \dots, \pm 2013 there is no number equal to 00 because there are 10071007 odd numbers, namely 1,3,,20131, 3, \dots, 2013. The result of addition and subtraction of these 10071007 numbers is an odd number, and the result of addition or subtraction of odd and even numbers is odd too. Therefore, we conclude that Iσ2014|I_\sigma| \neq 2014 and Iσ|I_\sigma| takes values 1,2,,20131, 2, \dots, 2013 only.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.