2017 AIME II Problem 11

Attempt Problem 11 of the 2017 AIME II below, then check your answer against the professionally curated solution 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 problems are used with official legal permission of the Mathematical Association of America (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).

Answer: 544
Concepts:graph theorycomplementary countinginclusion-exclusion
Difficulty rating: 3060
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 10#10
Full Exam

Problem 11 in Other Years