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

Revision as of 14:05, 17 June 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 1

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}$

Solution 2

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

If $6$ is the second number, then the first number can be $2, 3, 4,$ or $5$ , and there are $4!$ ways to place the other $4$ numbers. $4 \cdot 4! = 96$ ways.

If $6$ is the third number, then we cannot have the following:

1 _ 6 _ _ _ $\implies$ 24 ways

2 1 6 _ _ _ $\implies$ 6 ways

$120 - 24 - 6 = 90$ ways

If $6$ is the fourth number, then we cannot have the following: 1 _ _ 6 _ _ $\implies$ 24 ways

2 1 _ 6 _ _ $\implies$ 6 ways

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

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

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

$120 - 24 - 6 - 2 - 2 - 2 = 84$ ways

If $6$ is the fifth number, then we cannot have the following:

_ _ _ _ 6 5 $\implies$ 24 ways

1 5 _ _ 6 _ $\implies$ 6 ways

1 _ 5 _ 6 _ $\implies$ 6 ways

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

1 _ _ 5 6 _ $\implies$ 6 ways

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

2 3 1 5 6 4, 3 1 2 5 6 4, 3 2 1 5 6 4 $\implies$ 3 ways

$120 - 24 - 6 - 6 - 2 - 6 - 2 - 3 = 71$ ways

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

Solution 3 (needs explanation)

The answer is $\frac{6!}{2} + 5! - 4! + 3! - 2! + 1! = \boxed{\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.

@@ Line 124: / Line 124: @@
 ==Solution 3 (needs explanation)==
-The answer is <math>\frac{6!}{2} + 5! - 4! + 3! - 2! + 1! = \boxed{461}</math>.
+The answer is <math>\frac{6!}{2} + 5! - 4! + 3! - 2! + 1! = \boxed{\boxed{461}}</math>.
 {{AIME box|year=2018|n=II|num-b=10|num-a=12}}
 {{MAA Notice}}

Page

Toolbox

Search