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

Difference between revisions of "2018 AIME II Problems/Problem 11"

(Created page with "==Problem== Find the number of permutations of <math>1, 2, 3, 4, 5, 6</math> such that for each <math>k</math> with <math>1</math> <math>\leq</math> <math>k</math> <math>\leq...")
 
Line 2: Line 2:
  
 
Find the number of permutations of <math>1, 2, 3, 4, 5, 6</math> such that for each <math>k</math> with <math>1</math> <math>\leq</math> <math>k</math> <math>\leq</math> <math>5</math>, at least one of the first <math>k</math> terms of the permutation is greater than <math>k</math>.
 
Find the number of permutations of <math>1, 2, 3, 4, 5, 6</math> such that for each <math>k</math> with <math>1</math> <math>\leq</math> <math>k</math> <math>\leq</math> <math>5</math>, at least one of the first <math>k</math> terms of the permutation is greater than <math>k</math>.
 +
 +
==Solution==
 +
 +
If the first number is 6, then there are no restrictions. There are 5!, or 120 ways to place the other 5 numbers
 +
 +
 +
If the first number is 5, 6 can go in four places, and there are 4! ways to place the other 4 numbers. 4 * 4! = 96 ways.
 +
 +
 +
If the first number is 4, ....
 +
 +
4 6 _ _ _ _ -> 24 ways
 +
 +
4 _ 6 _ _ _ -> 24 ways
 +
 +
4 _ _ 6 _ _ -> 24 ways
 +
 +
4 _ _ _ 6 _ -> 5 must go between 4 and 6, so there are 3 * 3! = 18 ways.
 +
 +
24 + 24 + 24 + 18 = 90 ways if 4 is first.
 +
 +
 +
If the first number is 3, ....
 +
 +
3 6 _ _ _ _ -> 24 ways
 +
 +
3 _ 6 _ _ _ -> 24 ways
 +
 +
3 1 _ 6 _ _ -> 4 ways
 +
 +
3 2 _ 6 _ _ -> 4 ways
 +
 +
3 4 _ 6 _ _ -> 6 ways
 +
 +
3 5 _ 6 _ _ -> 6 ways
 +
 +
3 5 _ _ 6 _ -> 6 ways
 +
 +
3 _ 5 _ 6 _ -> 6 ways
 +
 +
3 _ _ 5 6 _ -> 4 ways
 +
 +
24 + 24 + 4 + 4 + 6 + 6 + 6 + 6 + 4 = 84 ways
 +
 +
 +
If the first number is 2, ....
 +
 +
2 6 _ _ _ _ -> 24 ways
 +
 +
2 _ 6 _ _ _ -> 18 ways
 +
 +
2 3 _ 6 _ _ -> 4 ways
 +
 +
2 4 _ 6 _ _ -> 4 ways
 +
 +
2 4 _ 6 _ _ -> 6 ways
 +
 +
2 5 _ 6 _ _ -> 6 ways
 +
 +
2 5 _ _ 6 _ -> 6 ways
 +
 +
2 _ 5 _ 6 _ -> 4 ways
 +
 +
2 4 _ 5 6 _ -> 2 ways
 +
 +
2 3 4 5 6 1 -> 1 way
 +
 +
 +
24 + 18 + 4 + 4 + 6 + 6 + 6 + 4 + 2 + 1 = 71 ways
 +
 +
 +
Grand Total : 120 + 96 + 90 + 84 + 71 = <math>\boxed{461}</math>
  
 
{{AIME box|year=2018|n=II|num-b=10|num-a=12}}
 
{{AIME box|year=2018|n=II|num-b=10|num-a=12}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 12:15, 24 March 2018

Problem

Find the number of permutations of $1, 2, 3, 4, 5, 6$ such that for each $k$ with $1$ $\leq$ $k$ $\leq$ $5$, at least one of the first $k$ terms of the permutation is greater than $k$.

Solution

If the first number is 6, then there are no restrictions. There are 5!, or 120 ways to place the other 5 numbers


If the first number is 5, 6 can go in four places, and there are 4! ways to place the other 4 numbers. 4 * 4! = 96 ways.


If the first number is 4, ....

4 6 _ _ _ _ -> 24 ways

4 _ 6 _ _ _ -> 24 ways

4 _ _ 6 _ _ -> 24 ways

4 _ _ _ 6 _ -> 5 must go between 4 and 6, so there are 3 * 3! = 18 ways.

24 + 24 + 24 + 18 = 90 ways if 4 is first.


If the first number is 3, ....

3 6 _ _ _ _ -> 24 ways

3 _ 6 _ _ _ -> 24 ways

3 1 _ 6 _ _ -> 4 ways

3 2 _ 6 _ _ -> 4 ways

3 4 _ 6 _ _ -> 6 ways

3 5 _ 6 _ _ -> 6 ways

3 5 _ _ 6 _ -> 6 ways

3 _ 5 _ 6 _ -> 6 ways

3 _ _ 5 6 _ -> 4 ways

24 + 24 + 4 + 4 + 6 + 6 + 6 + 6 + 4 = 84 ways


If the first number is 2, ....

2 6 _ _ _ _ -> 24 ways

2 _ 6 _ _ _ -> 18 ways

2 3 _ 6 _ _ -> 4 ways

2 4 _ 6 _ _ -> 4 ways

2 4 _ 6 _ _ -> 6 ways

2 5 _ 6 _ _ -> 6 ways

2 5 _ _ 6 _ -> 6 ways

2 _ 5 _ 6 _ -> 4 ways

2 4 _ 5 6 _ -> 2 ways

2 3 4 5 6 1 -> 1 way


24 + 18 + 4 + 4 + 6 + 6 + 6 + 4 + 2 + 1 = 71 ways


Grand Total : 120 + 96 + 90 + 84 + 71 = $\boxed{461}$

2018 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_II_Problems/Problem_11&oldid=93468"