2017 AIME II Problem 11

Below is the professionally curated solution for Problem 11 of the 2017 AIME II, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2017 AIME II solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:graph theorycomplementary countinginclusion-exclusion

Difficulty rating: 3060

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).

Solution:

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.

← Problem 10Full ExamProblem 12

Problem 11 in Other Years