2021 AMC 10A Spring 第 20 题

Question

将数列

1

，

2

，

3

，

4

，

5

重新排列，有多少种排列使得不存在连续三项递增，也不存在连续三项递减？

In how many ways can the sequence

1,

2,

3,

4,

5

be rearranged so that no three consecutive terms are increasing and no three consecutive terms are decreasing?

10

18

24

32

44

答案：D

知识点：有限制的排列双射

难度评级：1950

小提示：

有效排列中，相邻项之间的大小比较符号必须交替。

A valid permutation must have comparison signs that alternate

大提示：

先数“升降升降”型排列，再用对称性得到相反型。

Count the up-down-up-down permutations and use symmetry for the reverse pattern

视频讲解：

Click to load, then click again to play

文字解答：

一个排列有效，当且仅当相邻两项之间的四个比较符号交替出现。因此这些符号只能是升降升降或降升降升。

对升降升降型，最大的数

5

必须位于第

2

位或第

4

位。若它在第

2

位，设第

4

位上的数为

r

。它的两个相邻数必须是小于

r

的两个不同的数，共有

(r-1)(r-2)

种排法。对

r=1,2,3,4

求和，得到

0+0+2+6=8

个排列。由对称性，当

5

在第

4

位时另有

8

个，所以这种比较模式共有

16

个排列。

把每个数

x

替换为

6-x

，可与降升降升型一一对应，所以另有

16

个。

总共有

16+16=32

个有效排列。

所以正确答案是 D。

A permutation is valid exactly when the four comparison signs between consecutive terms alternate. Thus the signs must be either up-down-up-down or down-up-down-up.

For the up-down-up-down pattern, the largest entry

5

must be in position

2

or position

4.

If it is in position

2,

let the entry in position

4

be

r.

Its two neighbors must be distinct numbers less than

r,

which can be ordered in

(r-1)(r-2)

ways. Summing over

r=1,2,3,4

gives

0+0+2+6=8

permutations. By symmetry there are another

8

when

5

is in position

4,

for a total of

16

with this comparison pattern.

Replacing every entry

x

by

6-x

gives a bijection to the down-up-down-up permutations, so there are another

16.

The total number of valid rearrangements is

16+16=32.

Thus, D is the correct answer.