Maths Olympiad Prep

Library / /21 of 92

Combinatorics Difficulty 6.0 AIME, harder Prove it Iran

Find the maximum number of permutations of the set {1,2,,2014}\{1, 2, \ldots, 2014\} such that for each two distinct numbers aa and bb of this set, one could find at most one permutation in which bb has appeared exactly after aa.

Solution

There are 2014×20132014 \times 2013 ordered pairs (a,b)(a, b) such that 1ab20141 \le a \ne b \le 2014. On the other hand, there are 20132013 consecutive pairs in each permutation. Therefore, the number of such permutations is at most 20142014.

Consider the 20142014 permutations of the form
σi=(2014+i,1+i,2013+i,2+i,,1007+i,1006+i),1i2014, \sigma_i = (2014 + i, 1 + i, 2013 + i, 2 + i, \ldots, 1007 + i, 1006 + i), \quad 1 \le i \le 2014,
where all the numbers are considered modulo 20142014 (20142014 itself being an exception). We claim that for each aba \ne b there is exactly one index ii such that bb has appeared after aa in σi\sigma_i. To prove it, note that the differences of consecutive terms in all these permutations are
(2013,2,2011,4,2009,6,,2012,1), (2013, 2, 2011, 4, 2009, 6, \ldots, 2012, 1),
and all the numbers are modulo 20142014. So the position of bb and aa is uniquely determined by the value of bab-a and the index of permutation is uniquely determined by the value of bb.

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.