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"

m (→‎Problem)
m (→‎Solution 1)
 
Line 5: Line 5:
 
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>.
 
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.
+
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>  
 
<math>98+196+4753=\boxed{5047}</math>  
  
 
~cassphe
 
~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"