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
解答:
方向分配可行,当且仅当没有城镇的四条道路全入或全出。一方面很明显:全入的城镇无法离开, 全出的城镇无法到达。反过来,假设每个城镇都有入路和出路,但从城镇 。 无法到达城镇 。 令 为从 可到达的城镇集合(包括 ),令 为可以到达 的城镇集合 (包括 )。这两个集合不相交, 中城镇的每条出路都仍留在 中, 中城镇的 每条入路都来自 中。因为 有出路,所以 ,同理 ; 又因为 ,两个集合中有一个恰好有两个城镇。若 , 则 和 的出路都必须留在 内,迫使它们之间唯一的道路同时指向两个方向,矛盾 ( 的情况对称)。
现在在 种总方向分配中计数有坏城镇的情况。选择一个城镇全出( 种), 剩余 条道路任意定向,得到 种分配; 并且全出城镇最多只有一个。同理,有全入城镇的分配也有 种。同时有全出和全入城镇的分配 被重复计数:选全出城镇( 种),选全入城镇( 种),其他 条道路任意定向, 有 。 种。因此失败的分配有 种。
可行的数量为 。
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 cannot be reached from town Let be the set of towns reachable from (including ) and the set of towns from which is reachable (including ). These sets are disjoint, every outbound road of a town in stays inside and every inbound road of a town in comes from inside Since has an outbound road, and similarly as one of the two sets has exactly two towns. If the outbound roads of and of must both stay inside forcing the single road between them to point both ways — a contradiction (and is symmetric).
Now count assignments with a bad town among the total. Choosing a town to be all-outbound ( ways) and orienting the remaining roads freely gives assignments, and there can be at most one all-outbound town. Similarly assignments have an all-inbound town. Assignments with both are counted twice: choose the all-outbound town (), the all-inbound town (), and the other roads freely, So assignments fail.
The number that work is
其他年份的第 11 题
1997 AIME · 1998 AIME · 1999 AIME · 2000 AIME I · 2000 AIME II · 2001 AIME I · 2001 AIME II · 2002 AIME I · 2002 AIME II · 2003 AIME I · 2003 AIME II · 2004 AIME I · 2004 AIME II · 2005 AIME I · 2005 AIME II · 2006 AIME I · 2006 AIME II · 2007 AIME I · 2007 AIME II · 2008 AIME I · 2008 AIME II · 2009 AIME I · 2009 AIME II · 2010 AIME I · 2010 AIME II · 2011 AIME I · 2011 AIME II · 2012 AIME I · 2012 AIME II · 2013 AIME I · 2013 AIME II · 2014 AIME I · 2014 AIME II · 2015 AIME I · 2015 AIME II · 2016 AIME I · 2016 AIME II · 2017 AIME I · 2018 AIME I · 2018 AIME II · 2019 AIME I · 2019 AIME II · 2020 AIME I · 2020 AIME II · 2021 AIME I · 2021 AIME II · 2022 AIME I · 2022 AIME II · 2023 AIME I · 2023 AIME II · 2024 AIME I · 2024 AIME II · 2025 AIME I · 2025 AIME II · 2026 AIME I · 2026 AIME II