Difference between revisions of "2017 MPFG Problem 14"
m (→Problem) |
|||
| Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
| − | A <math>\textit{permutation}</math> of a finite set <math>S</math> is a one-to-one function from <math>S</math> to <math>S</math>. Given a permutation <math>f</math> of the set <math>{1,2,...,100}</math>, define the displacement of <math>f</math> to be the sum < | + | A <math>\textit{permutation}</math> of a finite set <math>S</math> is a one-to-one function from <math>S</math> to <math>S</math>. Given a permutation <math>f</math> of the set <math>{1,2,...,100}</math>, define the displacement of <math>f</math> to be the sum <cmath>\sum_{i=1}^{100}\left|f(i)-i\right|</cmath> How many permutations of <math>{1,2,...,100}</math> have displacement <math>4</math>? |
==Solution 1== | ==Solution 1== | ||
Revision as of 08:45, 22 October 2025
Problem
A 
of a finite set 
is a one-to-one function from to . Given a permutation 
of the set 
, define the displacement of to be the sum ![\[\sum_{i=1}^{100}\left|f(i)-i\right|\]](http://latex.artofproblemsolving.com/1/e/8/1e8cd60576fae6a107e5dda0166d8b17a1fbd50f.png)
How many permutations of have displacement 
?
Solution 1
Displacement is basically the sum of error of each place in the permutation. Consider how to split the displacement of : 
.
We may have 
numbers with a difference of switching location, 
consecutive numbers rotated, and sets of consecutive numbers switching location. The first situation gives us 
permutations, the second situation gives us 
permutations, since the numbers can be "rotated" in two directions, and the third situation gives us 
permutations, selecting from the 
pile.
~cassphe
