2019 AIME II 第 5 题

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

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

5.

四位大使以及每位大使的一名顾问要坐在一张有 1212 把椅子的圆桌旁,椅子按顺序编号为 111212。每位大使必须坐在偶数编号的椅子上。每位顾问必须坐在与其大使相邻的椅子上。在这些条件下,88 个人共有 NN 种坐法。求 NN 除以 10001000 的余数。

Four ambassadors and one advisor for each of them are to be seated at a round table with 1212 chairs numbered in order 11 to 12.12. Each ambassador must sit in an even-numbered chair. Each advisor must sit in a chair adjacent to his or her ambassador. There are NN ways for the 88 people to be seated at the table under these conditions. Find the remainder when NN is divided by 1000.1000.

答案:520
知识点:环形排列有限制的排列分类讨论
难度评级:2650
解答:

共有 66 把偶数椅子形成一个环(椅子 1212 与椅子 11 相邻),每把奇数椅子都在两把相邻偶数椅子之间。大使占用六把偶数椅子中的 44 把,每位顾问必须在其大使旁边两把奇数椅子中选一把,且所有选择互不相同。对一段长度为 kk 的极大连续被占用偶数椅子,kk 位占用者要在接触这段的 k+1k + 1 把奇数椅子中选择;把每个选择记作左或右,只有当某人选右而邻座选左时会冲突,所以有效模式恰为若干个 LL 后接若干个 RR 的字符串,共 k+1k + 1 种。

现在按六个偶数位置中的两把空椅子分类。若它们相邻(66 种),被占用椅子形成一个长度 44 的块,给出 55 种模式。若它们隔着一把椅子(66 种),块大小为 1133,给出 24=82 \cdot 4 = 8 种模式。若它们相对(33 种),块大小为 2222,给出 33=93 \cdot 3 = 9 种模式。座位配置数为 65+68+39=1056 \cdot 5 + 6 \cdot 8 + 3 \cdot 9 = 105

最后,四对大使与顾问可以用 4!=244! = 24 种方式分配到四把选定的偶数椅子上,所以 N=10524=2520N = 105 \cdot 24 = 2520,除以 10001000 的余数为 520520

The six even chairs form a cycle (chair 1212 is adjacent to chair 11), and each odd chair lies between two consecutive even chairs. The ambassadors occupy 44 of the 66 even chairs, and each advisor must take one of the two odd chairs flanking their ambassador, with all choices distinct. For a maximal block of kk consecutive occupied even chairs, the kk occupants choose among the k+1k + 1 odd chairs touching the block; recording each choice as left or right, a conflict occurs exactly when someone picks right and their neighbor picks left, so the valid patterns are the strings of LLs followed by RRs: k+1k + 1 of them.

Now case on the two empty even chairs among the six positions. If they are adjacent (66 ways), the occupied chairs form one block of 4,4, giving 55 patterns. If they are separated by one chair (66 ways), the blocks have sizes 11 and 3,3, giving 24=82 \cdot 4 = 8 patterns. If they are opposite (33 ways), the blocks have sizes 22 and 2,2, giving 33=93 \cdot 3 = 9 patterns. The number of seat configurations is 65+68+39=105.6 \cdot 5 + 6 \cdot 8 + 3 \cdot 9 = 105.

Finally, the four ambassador-advisor pairs can be assigned to the four chosen even chairs in 4!=244! = 24 ways, so N=10524=2520,N = 105 \cdot 24 = 2520, and the remainder modulo 10001000 is 520.520.

← 第 4 题#4
完整试卷

其他年份的第 5 题