Find the maximum number of permutations of the set such that for each two distinct numbers and of this set, one could find at most one permutation in which has appeared exactly after .
Solution
There are ordered pairs such that . On the other hand, there are consecutive pairs in each permutation. Therefore, the number of such permutations is at most .
Consider the permutations of the form
where all the numbers are considered modulo ( itself being an exception). We claim that for each there is exactly one index such that has appeared after in . To prove it, note that the differences of consecutive terms in all these permutations are
and all the numbers are modulo . So the position of and is uniquely determined by the value of and the index of permutation is uniquely determined by the value of .
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.