2017 AIME II 第 11 题

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

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

11.

五个城镇由道路系统连接。每一对城镇之间恰好有一条道路。求有多少种方法把所有道路改成单行道, 使得仍然可以从任意一个城镇沿道路到达任意另一个城镇(途中可以经过其他城镇)。

Five towns are connected by a system of roads. There is exactly one road connecting each pair of towns. Find the number of ways there are to make all the roads one-way in such a way that it is still possible to get from any town to any other town using the roads (possibly passing through other towns on the way).

答案:544
知识点:图论补集计数容斥原理
难度评级:3060
解答:

方向分配可行,当且仅当没有城镇的四条道路全入或全出。一方面很明显:全入的城镇无法离开, 全出的城镇无法到达。反过来,假设每个城镇都有入路和出路,但从城镇 AA。 无法到达城镇 BB。 令 SS 为从 AA 可到达的城镇集合(包括 AA),令 TT 为可以到达 BB 的城镇集合 (包括 BB)。这两个集合不相交,SS 中城镇的每条出路都仍留在 SS 中,TT 中城镇的 每条入路都来自 TT 中。因为 AA 有出路,所以 S2|S| \ge 2,同理 T2|T| \ge 2; 又因为 S+T5|S| + |T| \le 5,两个集合中有一个恰好有两个城镇。若 S={A,X}S = \{A, X\}, 则 AAXX 的出路都必须留在 SS 内,迫使它们之间唯一的道路同时指向两个方向,矛盾 (T=2|T| = 2 的情况对称)。

现在在 210=10242^{10} = 1024 种总方向分配中计数有坏城镇的情况。选择一个城镇全出(55 种), 剩余 (42)=6\binom{4}{2} = 6 条道路任意定向,得到 526=3205 \cdot 2^6 = 320 种分配; 并且全出城镇最多只有一个。同理,有全入城镇的分配也有 320320 种。同时有全出和全入城镇的分配 被重复计数:选全出城镇(55 种),选全入城镇(44 种),其他 33 条道路任意定向, 有 5423=1605 \cdot 4 \cdot 2^3 = 160。 种。因此失败的分配有 320+320160=480320 + 320 - 160 = 480 种。

可行的数量为 1024480=5441024 - 480 = 544

The assignment works if and only if no town has all four roads inbound or all four outbound. One direction is clear: an all-inbound town cannot be left, and an all-outbound town cannot be reached. Conversely, suppose every town has an inbound and an outbound road, yet town BB cannot be reached from town A.A. Let SS be the set of towns reachable from AA (including AA) and TT the set of towns from which BB is reachable (including BB). These sets are disjoint, every outbound road of a town in SS stays inside S,S, and every inbound road of a town in TT comes from inside T.T. Since AA has an outbound road, S2,|S| \ge 2, and similarly T2;|T| \ge 2; as S+T5,|S| + |T| \le 5, one of the two sets has exactly two towns. If S={A,X},S = \{A, X\}, the outbound roads of AA and of XX must both stay inside S,S, forcing the single road between them to point both ways — a contradiction (and T=2|T| = 2 is symmetric).

Now count assignments with a bad town among the 210=10242^{10} = 1024 total. Choosing a town to be all-outbound (55 ways) and orienting the remaining (42)=6\binom{4}{2} = 6 roads freely gives 526=3205 \cdot 2^6 = 320 assignments, and there can be at most one all-outbound town. Similarly 320320 assignments have an all-inbound town. Assignments with both are counted twice: choose the all-outbound town (55), the all-inbound town (44), and the other 33 roads freely, 5423=160.5 \cdot 4 \cdot 2^3 = 160. So 320+320160=480320 + 320 - 160 = 480 assignments fail.

The number that work is 1024480=544.1024 - 480 = 544.

← 第 10 题#10
完整试卷

其他年份的第 11 题