Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus
During AMC testing, the AoPS Wiki is in read-only mode and no edits can be made.

Difference between revisions of "2017 MPFG Problem 14"

(Created page with "==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</mat...")
 
m (→‎Solution 1)
 
(2 intermediate revisions by the same user not shown)
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 <math>\sum_{i=1}^{100}\left|f(i)-i\right|</math>. How many permutations of <math>{1,2,...,100}</math> have displacement <math>4</math>?
+
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==
 +
Displacement is basically the sum of error of each place in the permutation. Consider how to split the displacement of <math>4</math>: <math>4 = 2+2 = 1+1+2 = 1+1+1+1</math>.
 +
 
 +
We may have <math>2</math> numbers with a difference of <math>2</math> switching location, <math>3</math> consecutive numbers rotated, and <math>2</math> sets of <math>2</math> consecutive numbers switching location. The first situation gives us <math>\{(1,3),(2,4),...,(98,100)\} = 98</math> permutations, the second situation gives us <math>\{(1,2,3),(2,3,4),...,(98,99,100)\} = 2\cdot 98 = 196</math> permutations, since the <math>3</math> numbers can be "rotated" in two directions, and the third situation gives us <math>{98\choose 2} = 4753</math> permutations, selecting <math>2</math> from the <math>\{(1,3),...,(98,100)\}</math> pile.
 +
 
 +
<math>98+196+4753=\boxed{5047}</math>
 +
 
 +
~cassphe

Latest revision as of 08:49, 22 October 2025

Problem

A $\textit{permutation}$ of a finite set $S$ is a one-to-one function from $S$ to $S$. Given a permutation $f$ of the set ${1,2,...,100}$, define the displacement of $f$ to be the sum \[\sum_{i=1}^{100}\left|f(i)-i\right|\] How many permutations of ${1,2,...,100}$ have displacement $4$?

Solution 1

Displacement is basically the sum of error of each place in the permutation. Consider how to split the displacement of $4$: $4 = 2+2 = 1+1+2 = 1+1+1+1$.

We may have $2$ numbers with a difference of $2$ switching location, $3$ consecutive numbers rotated, and $2$ sets of $2$ consecutive numbers switching location. The first situation gives us $\{(1,3),(2,4),...,(98,100)\} = 98$ permutations, the second situation gives us $\{(1,2,3),(2,3,4),...,(98,99,100)\} = 2\cdot 98 = 196$ permutations, since the $3$ numbers can be "rotated" in two directions, and the third situation gives us ${98\choose 2} = 4753$ permutations, selecting $2$ from the $\{(1,3),...,(98,100)\}$ pile.

$98+196+4753=\boxed{5047}$

~cassphe

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_MPFG_Problem_14&oldid=263865"