Difference between revisions of "2017 AIME II Problems/Problem 11"
Vincentfang (talk | contribs) (→Solution) |
Claudeaops (talk | contribs) (Extension) |
||
Line 41: | Line 41: | ||
=See Also= | =See Also= | ||
+ | Another way to state this problem is finding the number of strongly connected labeled tournaments on <math>5</math> nodes. Finding a strongly connected labeled tournament is the same as finding a way to make all the roads one-way such that there is always a way to get from one town to another. [http://oeis.org/A054946 This link] gives the number of strongly connected labeled tournaments on <math>n</math> nodes for small <math>n</math>. | ||
{{AIME box|year=2017|n=II|num-b=10|num-a=12}} | {{AIME box|year=2017|n=II|num-b=10|num-a=12}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 14:13, 28 February 2018
Problem
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
It is obvious that any configuration of one-way roads which contains a town whose roads all lead into it or lead out of it cannot satisfy the given. We claim that any configuration which does not have a town whose roads all lead into it or lead out of it does satisfy the given conditions. Now we show that a loop of or more towns exist. Pick a town, then choose a neighboring town to travel to
times. Of these
towns visited, at least two of them must be the same; therefore there must exist a loop of
or more towns because a loop of
towns cannot exist. We want to show that the loop can be reached from any town, and any town can be reached from the loop.
. The loop has
towns.
Clearly every town can be reached by going around the loop.
. The loop has
towns.
The town not on the loop must have a road leading to it. This road comes from a town on the loop. Therefore this town can be reached from the loop. This town not on the loop must also have a road leading out of it. This road leads to a town on the loop. Therefore the loop can be reached from the town.
. The loop has
towns.
There are two towns not on the loop; call them Town
and Town
. Without loss of generality assume
leads to
. Because a road must lead to
, the town where this road comes from must be on the loop. Therefore
and therefore
can be reached from the loop. Because a road must lead out of
, the town it leads to must be on the loop. Therefore the loop can be reached from
and also
.
The number of good configurations is the total number of configurations minus the number of bad configurations. There are total configurations. To find the number of bad configurations in which a town exists such that all roads lead to it, there are
ways to choose this town and
ways to assign the six other roads that do not connect to this town. The same logic is used to find the number of bad configurations in which a town exists such that all roads lead out of it. It might be tempting to conclude that there are
bad configurations, but the configurations in which there exists a town such that all roads lead to it and a town such that all roads lead out of it are overcounted. There are
ways to choose the town for which all roads lead to it,
ways to choose the town for which all roads lead out of it, and
ways to assign the remaining
roads not connected to either of these towns. Therefore, the answer is
.
Solution 2 (complementary counting)
The only way a town does not meet the conditions in the question is if the town has either all roads leading towards it or all roads leading away from it. For example, if all roads lead away from Town , there is no way to reach the town starting from Towns
,
,
, or
. If all roads lead towards Town
, there is no way to reach any other town starting from Town
. Thus, we will count the ways this occurs.
. WLOG, Town
has all roads leading towards it.
In this case, the four roads leading to Town have already been determined. There are
roads that have not been given directions. Each of these roads have
options: it can lead towards one town or the other town. Thus, there are
arrangements of roads.
However, we must consider the
towns in which this scenario can occur: there are
arrangements.
. WLOG, Town
has all roads leading away.
Notice that this case is symmetrical to the first case. Thus, there are arrangements.
. WLOG, Town
has all roads leading towards it and Town
has all roads leading away.
We must check for double-counted cases. Drawing a flow diagram, we see that this case determines roads. For the undetermined
roads, there are
arrangements. However, we must again consider the different ways that this case can occur. There are
choices for towns with roads leading towards it
choices for roads leading away. Thus, the total double-counted cases are
arrangements.
We must subtract the cases we counted from the total. There are a total of roads with
possible arrangements each.
Therefore the total number of cases is
, and the number of cases that meet the conditions is
arrangements.
~ jf
See Also
Another way to state this problem is finding the number of strongly connected labeled tournaments on nodes. Finding a strongly connected labeled tournament is the same as finding a way to make all the roads one-way such that there is always a way to get from one town to another. This link gives the number of strongly connected labeled tournaments on
nodes for small
.
2017 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 10 |
Followed by Problem 12 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.