2018 AIME II Problems/Problem 11

Problem

Find the number of permutations of such that for each with , at least one of the first terms of the permutation is greater than .

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 =

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