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"
(→‎Solution)
Line 5: Line 5:
 
==Solution==
 
==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 <math>6</math>, then there are no restrictions. There are <math>5!</math>, or <math>120</math> ways to place the other <math>5</math> 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 <math>5</math>, <math>6</math> can go in four places, and there are <math>4!</math> ways to place the other <math>4</math> numbers. <math>4 \cdot 4! = 96</math> ways.
  
  
−
If the first number is 4, ....
+
If the first number is <math>4</math>, ....
  
−
4 6 _ _ _ _ -> 24 ways
+
4 6 _ _ _ _ <math>\implies</math> 24 ways
  
−
4 _ 6 _ _ _ -> 24 ways
+
4 _ 6 _ _ _ <math>\implies</math> 24 ways
  
−
4 _ _ 6 _ _ -> 24 ways
+
4 _ _ 6 _ _ <math>\implies</math> 24 ways
  
−
4 _ _ _ 6 _ -> 5 must go between 4 and 6, so there are 3 * 3! = 18 ways.
+
4 _ _ _ 6 _ <math>\implies</math> 5 must go between <math>4</math> and <math>6</math>, so there are <math>3 \cdot 3! = 18</math> ways.
  
 
24 + 24 + 24 + 18 = 90 ways if 4 is first.
 
24 + 24 + 24 + 18 = 90 ways if 4 is first.
  
  
−
If the first number is 3, ....
+
If the first number is <math>3</math>, ....
  
−
3 6 _ _ _ _ -> 24 ways
+
3 6 _ _ _ _ <math>\implies</math> 24 ways
  
−
3 _ 6 _ _ _ -> 24 ways
+
3 _ 6 _ _ _ <math>\implies</math> 24 ways
  
−
3 1 _ 6 _ _ -> 4 ways  
+
3 1 _ 6 _ _ <math>\implies</math> 4 ways  
  
−
3 2 _ 6 _ _ -> 4 ways
+
3 2 _ 6 _ _ <math>\implies</math> 4 ways
  
−
3 4 _ 6 _ _ -> 6 ways
+
3 4 _ 6 _ _ <math>\implies</math> 6 ways
  
−
3 5 _ 6 _ _ -> 6 ways
+
3 5 _ 6 _ _ <math>\implies</math> 6 ways
  
−
3 5 _ _ 6 _ -> 6 ways
+
3 5 _ _ 6 _ <math>\implies</math> 6 ways
  
−
3 _ 5 _ 6 _ -> 6 ways
+
3 _ 5 _ 6 _ <math>\implies</math> 6 ways
  
−
3 _ _ 5 6 _ -> 4 ways
+
3 _ _ 5 6 _ <math>\implies</math> 4 ways
  
−
24 + 24 + 4 + 4 + 6 + 6 + 6 + 6 + 4 = 84 ways
+
<math>24 + 24 + 4 + 4 + 6 + 6 + 6 + 6 + 4 = 84</math> ways
  
  
−
If the first number is 2, ....
+
If the first number is <math>2</math>, ....
  
−
2 6 _ _ _ _ -> 24 ways
+
2 6 _ _ _ _ <math>\implies</math> 24 ways
  
−
2 _ 6 _ _ _ -> 18 ways  
+
2 _ 6 _ _ _ <math>\implies</math> 18 ways  
  
−
2 3 _ 6 _ _ -> 4 ways
+
2 3 _ 6 _ _ <math>\implies</math> 4 ways
  
−
2 4 _ 6 _ _ -> 4 ways
+
2 4 _ 6 _ _ <math>\implies</math> 4 ways
  
−
2 4 _ 6 _ _ -> 6 ways
+
2 4 _ 6 _ _ <math>\implies</math> 6 ways
  
−
2 5 _ 6 _ _ -> 6 ways
+
2 5 _ 6 _ _ <math>\implies</math> 6 ways
  
−
2 5 _ _ 6 _ -> 6 ways
+
2 5 _ _ 6 _ <math>\implies</math> 6 ways
  
−
2 _ 5 _ 6 _ -> 4 ways
+
2 _ 5 _ 6 _ <math>\implies</math> 4 ways
  
−
2 4 _ 5 6 _ -> 2 ways
+
2 4 _ 5 6 _ <math>\implies</math> 2 ways
  
−
2 3 4 5 6 1 -> 1 way
+
2 3 4 5 6 1 <math>\implies</math> 1 way
  
  
−
24 + 18 + 4 + 4 + 6 + 6 + 6 + 4 + 2 + 1 = 71 ways
+
<math>24 + 18 + 4 + 4 + 6 + 6 + 6 + 4 + 2 + 1 = 71</math> ways
  
  
−
Grand Total : 120 + 96 + 90 + 84 + 71 = <math>\boxed{461}</math>
+
Grand Total : <math>120 + 96 + 90 + 84 + 71 = </math><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 19:24, 26 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 \cdot 4! = 96$ ways.


If the first number is $4$, ....

4 6 _ _ _ _ $\implies$ 24 ways

4 _ 6 _ _ _ $\implies$ 24 ways

4 _ _ 6 _ _ $\implies$ 24 ways

4 _ _ _ 6 _ $\implies$ 5 must go between $4$ and $6$, so there are $3 \cdot 3! = 18$ ways.

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


If the first number is $3$, ....

3 6 _ _ _ _ $\implies$ 24 ways

3 _ 6 _ _ _ $\implies$ 24 ways

3 1 _ 6 _ _ $\implies$ 4 ways

3 2 _ 6 _ _ $\implies$ 4 ways

3 4 _ 6 _ _ $\implies$ 6 ways

3 5 _ 6 _ _ $\implies$ 6 ways

3 5 _ _ 6 _ $\implies$ 6 ways

3 _ 5 _ 6 _ $\implies$ 6 ways

3 _ _ 5 6 _ $\implies$ 4 ways

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


If the first number is $2$, ....

2 6 _ _ _ _ $\implies$ 24 ways

2 _ 6 _ _ _ $\implies$ 18 ways

2 3 _ 6 _ _ $\implies$ 4 ways

2 4 _ 6 _ _ $\implies$ 4 ways

2 4 _ 6 _ _ $\implies$ 6 ways

2 5 _ 6 _ _ $\implies$ 6 ways

2 5 _ _ 6 _ $\implies$ 6 ways

2 _ 5 _ 6 _ $\implies$ 4 ways

2 4 _ 5 6 _ $\implies$ 2 ways

2 3 4 5 6 1 $\implies$ 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=93524"