2020 AIME II 第 9 题

先试着解答 2020 AIME II 第 9 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2020 AIME II 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

9.

看演出时,Ayako、Billy、Carlos、Dahlia、Ehuang 和 Frank 按这个顺序坐在一排六把椅子上。 中场休息时,他们去厨房吃点心。回来后,他们坐回这六把椅子,使得如果两个人在休息前相邻, 那么休息后他们不相邻。求他们休息后可能选择的座位顺序数。

While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they came back, they sat on those six chairs in such a way that if two of them sat next to each other before the break, then they did not sit next to each other after the break. Find the number of possible seating orders they could have chosen after the break.

答案:90
知识点:有限制的排列容斥原理排列
难度评级:2840
解答:

按原座位顺序把朋友编号为 1166;我们要数 1,,61, \ldots, 6 的排列,使得没有两个连续整数相邻。 对五个数对 {i,i+1}\{i, i+1\} 中哪些被迫坐在一起使用容斥。若所选的 kk 个数对形成 rr 段极大连续整数段, 把每段粘成一个块(可按递增或递减两种方向排列),就得到 2r(6k)!2^r (6 - k)! 个包含所有所选相邻关系的坐法。

kk 统计:当 k=0k = 0 时,有 720720。当 k=1k = 1 时,五个集合,每个有 21202 \cdot 120,共 12001200。当 k=2k = 2 时,四个集合形成一段 (224)(2 \cdot 24),六个形成两段 (424)(4 \cdot 24),共 768768。当 k=3k = 3 时,三个集合形成一段 (26)(2 \cdot 6),六个形成两段 (46)(4 \cdot 6),一个形成三段 (86)(8 \cdot 6),共 228228。当 k=4k = 4 时,两个集合形成一段 (22)(2 \cdot 2),三个形成两段 (42)(4 \cdot 2),共 3232。当 k=5k = 5 时,一个集合,共 22

所求数量为 7201200+768720 - 1200 + 768 228+322=90- 228 + 32 - 2 = 90

Number the friends 11 through 66 in original seating order; we count orderings of 1,,61, \ldots, 6 in which no two consecutive integers are adjacent. Apply inclusion-exclusion over which of the five pairs {i,i+1}\{i, i+1\} are forced to sit together. If a chosen set of kk pairs forms rr maximal runs of consecutive integers, gluing each run into a block (orderable ascending or descending) gives 2r(6k)!2^r (6 - k)! seatings containing all chosen adjacencies.

Tallying by k:k: for k=0,k = 0, 720.720. For k=1,k = 1, five sets, each 2120,2 \cdot 120, total 1200.1200. For k=2,k = 2, four sets form one run (224)(2 \cdot 24) and six form two runs (424),(4 \cdot 24), total 768.768. For k=3,k = 3, three sets form one run (26),(2 \cdot 6), six form two runs (46),(4 \cdot 6), one forms three runs (86),(8 \cdot 6), total 228.228. For k=4,k = 4, two sets form one run (22)(2 \cdot 2) and three form two runs (42),(4 \cdot 2), total 32.32. For k=5,k = 5, one set, total 2.2.

The count is 7201200+768720 - 1200 + 768 228+322=90.- 228 + 32 - 2 = 90.

← 第 8 题#8
完整试卷

其他年份的第 9 题