Difference between revisions of "2017 AIME II Problems/Problem 11"
(→Solution 5) |
Mathboy282 (talk | contribs) (→Diagram) |
||
(15 intermediate revisions by 3 users not shown) | |||
Line 15: | Line 15: | ||
The number of good configurations is the total number of configurations minus the number of bad configurations. There are <math>2^{{5\choose2}}</math> total configurations. To find the number of bad configurations in which a town exists such that all roads lead to it, there are <math>5</math> ways to choose this town and <math>2^6</math> 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 <math>5 \cdot 2^6+5 \cdot 2^6</math> 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 <math>5</math> ways to choose the town for which all roads lead to it, <math>4</math> ways to choose the town for which all roads lead out of it, and <math>2^3</math> ways to assign the remaining <math>3</math> roads not connected to either of these towns. Therefore, the answer is <math>2^{{5\choose2}}-(5 \cdot 2^6+5 \cdot 2^6-5\cdot 4 \cdot 2^3)=\boxed{544}</math>. | The number of good configurations is the total number of configurations minus the number of bad configurations. There are <math>2^{{5\choose2}}</math> total configurations. To find the number of bad configurations in which a town exists such that all roads lead to it, there are <math>5</math> ways to choose this town and <math>2^6</math> 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 <math>5 \cdot 2^6+5 \cdot 2^6</math> 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 <math>5</math> ways to choose the town for which all roads lead to it, <math>4</math> ways to choose the town for which all roads lead out of it, and <math>2^3</math> ways to assign the remaining <math>3</math> roads not connected to either of these towns. Therefore, the answer is <math>2^{{5\choose2}}-(5 \cdot 2^6+5 \cdot 2^6-5\cdot 4 \cdot 2^3)=\boxed{544}</math>. | ||
+ | |||
+ | ===Diagram=== | ||
+ | [[File:2017AIMEII_P11_Diagram.JPG|400px]] | ||
+ | |||
+ | Note that this isn't necessarily a diagram of the actual sequence of roads (I haven't drawn in every pair of cities to be connected), but a simplified diagram that can be used to represent a visualized representation of the loops in the cases | ||
+ | '''mathboy282''' | ||
==Solution 2 (complementary counting)== | ==Solution 2 (complementary counting)== | ||
Line 71: | Line 77: | ||
Proof: | Proof: | ||
+ | |||
Part 1: If there is no town in this graph with a indegree or outdegree of 5, it is possible to reach all of the 4 other towns from any town in the graph | Part 1: If there is no town in this graph with a indegree or outdegree of 5, it is possible to reach all of the 4 other towns from any town in the graph | ||
Line 83: | Line 90: | ||
If the cycle has length 3: | If the cycle has length 3: | ||
WLOG, we can assume that the cycle is 1->2->3->1 and that the road between town 4 and town 5 is 4->5. Since 4 has at least one incoming road, there must be a town in the cycle that has an road to town 4. Since town 5 has at least one outgoing road, there must be a road from town 5 to some town in the cycle. Thus, it is possible to reach any other town starting from one town. | WLOG, we can assume that the cycle is 1->2->3->1 and that the road between town 4 and town 5 is 4->5. Since 4 has at least one incoming road, there must be a town in the cycle that has an road to town 4. Since town 5 has at least one outgoing road, there must be a road from town 5 to some town in the cycle. Thus, it is possible to reach any other town starting from one town. | ||
+ | |||
Part 2: If it is possible to reach all of the 4 other towns starting from any town, there can be no town with indegree or outdegree of 5. | Part 2: If it is possible to reach all of the 4 other towns starting from any town, there can be no town with indegree or outdegree of 5. | ||
Line 91: | Line 99: | ||
-ZHANALEX | -ZHANALEX | ||
+ | |||
+ | ==Solution 6== | ||
+ | |||
+ | We claim the following conditions: | ||
+ | |||
+ | -A path is invalid if a vertex <math>\omega</math> has no arcs leading to it. (1) | ||
+ | |||
+ | -A path is invalid if a vertex <math>\omega</math> has all arcs leading to it. (2) | ||
+ | |||
+ | -A path is always valid if it does not satisfy (1) and (2) and has a "cycle" of arcs of <math>\omega_1 \to \omega_2 \to \omega_3 \to \omega_1</math>. (3) | ||
+ | |||
+ | -(1) and (2) are sufficient to cover all invalid paths. | ||
+ | |||
+ | Call the vertices <math>\omega_1, \omega_2, \omega_3, \omega_4, \omega_5</math>. WLOG, let <math>\omega_1 \to \omega_2</math>. Then, WLOG let <math>\omega_2 \to \omega_3</math>. We have two ways to go from here: | ||
+ | |||
+ | If <math>\omega_3 \to \omega_1</math>, we call it a "cycle". | ||
+ | |||
+ | We will prove (3): | ||
+ | |||
+ | Notice that once <math>\omega_4, \omega_5</math> can reach one of the vertices on the "cycle", it can reach any of the other vertices on the same cycle simply by travelling along the arcs of the cycle. Additionally, one of <math>\omega_4, \omega_5</math> must be able to travel to the cycle. Consider that it cannot, then <math>\omega_3 \to \omega_4</math> and <math>\omega_5 \to \omega_4</math> are forced. Now, <math>\omega_4 \to \omega_1, \omega_2, \omega_3</math> which is on the cycle. Now, if <math>\omega_5 \to \omega_4</math>, it will also be able to travel to the cycle. Otherwise, the directed arc will directly travel to the cycle. Also, each of the vertices <math>\omega_1, \omega_2, \omega_3</math> will travel to <math>\omega_4, \omega_5</math>. | ||
+ | |||
+ | If our graph does not satisfy (1) and (2), <math>\omega_4, \omega_5</math> will connect to the cycle on both directions. This can be shown below: | ||
+ | |||
+ | Clearly <math>\omega_4, \omega_5</math> are connected. Assuming the graph does not satisfy (1) and (2), <math>\omega_4, \omega_5</math> are connected to the cycle consisting of <math>\omega_1, \omega_2, \omega_3</math>. WLOG, let <math>\omega_4 \to \omega_5</math>: | ||
+ | |||
+ | Again, to avoid (2), <math>\omega_5 \to \omega_a</math> where <math>a\in{1,2,3}</math>. Now to avoid (1), one of <math>\omega_a \to \omega_4, a\in{1,2,3}</math>. | ||
+ | |||
+ | Now it is clear that each vertex can go to any other vertex. This concludes our proof. | ||
+ | |||
+ | Say we try to avoid (3) so that WLOG <math>\omega_5 \to \omega_1</math>. If we keep trying to avoid a "cycle", <math>\omega_3 \to \omega_4</math> and <math>\omega_4 \to \omega_5</math> which is a cycle. | ||
+ | |||
+ | Therefore, if there is any path <math>\omega_a \to \omega_b \to \omega_c</math>, it will lead to a cycle and ultimately a valid path. The only way to avoid this is to have (1) or (2). | ||
+ | |||
+ | Consider (1): | ||
+ | |||
+ | WLOG, let <math>\omega_1</math> have no arcs leading to it. Then all other vertices will have an arc directed toward them away from <math>\omega_1</math>. Therefore, one path can have only 1 unique vertex that has no arcs leading to it. There are 5 ways to choose the vertex and <math>2^{\binom{5}{2}-4}=2^6</math> ways for the remaining 6 arcs since they can be directed in any way. There are <math>2^6\cdot5=320</math> paths for this condition. | ||
+ | |||
+ | Consider (2): | ||
+ | |||
+ | WLOG, let <math>\omega_1</math> have all arcs leading to it. Similarly, all other vertices will have an arc that is directed away from them and points to <math>\omega_1</math>. Therefore, only one unique vertex can have all arcs leading to it. There are 5 ways to choose the vertex and <math>2^{\binom{5}{2}-4}=2^6</math> ways for the remaining arcs. There are also <math>2^6\cdot5=320</math> paths for this condition. | ||
+ | |||
+ | However, we have overcounted paths that satisfy both (1) and (2). These paths will have one vertex that has all arcs leading to it and another that has all arcs directed away from it. There are <math>5\cdot4=20</math> ways to choose these 2 vertices, and the remaining <math>\binom{3}{2}=3</math> arcs each have 2 ways to be directed toward each other, so there are a total of <math>2^3\cdot 20=160</math> overlapping paths. | ||
+ | |||
+ | By PIE, the number of invalid cases is <math>320+320-160=480</math>. | ||
+ | |||
+ | The total number of cases is <math>2^{\binom{5}{2}}=2^{10}=1024</math> since there are 10 edges and each can go 2 ways. By complementary counting, the number of valid paths is just <math>1024-480=\boxed{544}</math> | ||
+ | |||
+ | -Magnetoninja | ||
=See Also= | =See Also= |
Latest revision as of 17:51, 6 January 2024
Contents
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
.
Diagram
Note that this isn't necessarily a diagram of the actual sequence of roads (I haven't drawn in every pair of cities to be connected), but a simplified diagram that can be used to represent a visualized representation of the loops in the cases mathboy282
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. (To show this, first note that there must always be a directed path that visits every town once, say
(Redei's Theorem). Taking cases, it can be seen that if
does not have all its roads leading, then
must have its roads leading into it.)
. 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
Solution 3
Assume the five towns are named A, B, C, D, and E. Draw roads that connect each of the five towns. First, figure out how many total roads there are with no restrictions. This would be , or
. Next, add together the number of restrictions (or incorrect cases) there are. One incorrect case happens if we can't get to one of the five towns. When that happens, any roads that connect that town with any of the other four towns must be one way. Four roads are invalidated (because they are one way) as, assuming we can't get to town A, roads AB, AC, AD, and AE would all be one way. Since there are
ways of choosing which town to restrict, there are
, or
restrictions in this case. The next case is when we can't get to two of the towns. Let's assume we don't want to get to towns A and B. Then, roads AC, AD, AE, BC, BD, and BE are all invalidated. Since there are
of choosing which two towns to restrict, there are
, or
restrictions in this case. Notice that when we restrict three towns, it is the same thing as restricting two towns. For example, if we restricted entry to towns C, D, and E from towns A and B, it's the same thing as if we restricted entry to towns A and B from towns C, D, and E, as the exact same roads are invalidated in both cases. Thus, our final answer is
arrangements.
Solution by IronicNinja~
Solution 4
As noted before, you can see that there are 2 ways that the condition cannot be met; it either has all roads leading into one city, or all roads leading out of one city. We then use complementary counting to count these cases, with PIE. Obviously there are ways to make roads (just draw a pentagon with all of the diagonals and assume that they are roads, and count the sides and then the diagonals). Then, make all roads leading in to another city. There are 4 roads leading into that city, so there are
ways to designate that. Given that there are 5 cities, and it can also be the ways to go out of the city, you get
ways NOT to get into the city. However, this disregards the case that 2 cities are like this, which is the PIE case. Quick inspection shows that there are no cases where 3 are like that, and inspection with le pentagon can also show you that there are
(because they can all lead in and all lead out)
(because there are 3 roads left to choose). In the end, this comes out to
-dragonon
Solution 5 (Graph Theory)
We use Claim 1 along with complementary counting.
Then, the number of valid cases is the total () minus the cases in which there are towns with indegree or outdegree 5.
Number of cases in which there is a node with indegree 5:
5 ways to choose which town has indegree 5 and for the remaining roads, they each have 2 possible statuses.
Similarly, the number of cases in which there is a node with outdegree 5 is also
The number of cases in which there is a node with indegree 5 and there is a node with outdegree 5:
Thus, answer = =
- Note: In this graph there can be at most one town with indegree 5 or outdegree 5.
Solution by ZHANALEX
Claim 1
Claim: If and only if there is no town in this graph with a indegree or outdegree of 5, it is possible to reach all of the 4 other towns from any town in the graph.
Proof:
Part 1: If there is no town in this graph with a indegree or outdegree of 5, it is possible to reach all of the 4 other towns from any town in the graph
Since every town has an outgoing road, there is definitely a cycle. (Since there are only n town, eventually you must come back to a town that is already visited) Since a cycle of length 2 is not possible in this problem, the cycle can have a length of 3, 4, or 5. If the cycle has length 5, then it is definitely possible to go from one town to any other town. Ex: If the cycle is 1->2->3->4->5->1, then it is clear that you can reach any other town from one town
If the cycle has length 4: WLOG, let 1->2->3->4->1 be the cycle. Since town 5 has at least one incoming road and one outgoing road, there is definitely an road from a town on the cycle to town 5. There must also be an road from town 5 to another town that is in the cycle. Thus, it is definitely possible to reach any other town from one town.
If the cycle has length 3: WLOG, we can assume that the cycle is 1->2->3->1 and that the road between town 4 and town 5 is 4->5. Since 4 has at least one incoming road, there must be a town in the cycle that has an road to town 4. Since town 5 has at least one outgoing road, there must be a road from town 5 to some town in the cycle. Thus, it is possible to reach any other town starting from one town.
Part 2: If it is possible to reach all of the 4 other towns starting from any town, there can be no town with indegree or outdegree of 5.
It is clear that you cannot have any town with indegree or outdegree of 5 or else that town would either be unreachable from the other towns or that town would be unable to reach any other town.
The proof is complete. (It is actually much simpler than it looks)
-ZHANALEX
Solution 6
We claim the following conditions:
-A path is invalid if a vertex has no arcs leading to it. (1)
-A path is invalid if a vertex has all arcs leading to it. (2)
-A path is always valid if it does not satisfy (1) and (2) and has a "cycle" of arcs of . (3)
-(1) and (2) are sufficient to cover all invalid paths.
Call the vertices . WLOG, let
. Then, WLOG let
. We have two ways to go from here:
If , we call it a "cycle".
We will prove (3):
Notice that once can reach one of the vertices on the "cycle", it can reach any of the other vertices on the same cycle simply by travelling along the arcs of the cycle. Additionally, one of
must be able to travel to the cycle. Consider that it cannot, then
and
are forced. Now,
which is on the cycle. Now, if
, it will also be able to travel to the cycle. Otherwise, the directed arc will directly travel to the cycle. Also, each of the vertices
will travel to
.
If our graph does not satisfy (1) and (2), will connect to the cycle on both directions. This can be shown below:
Clearly are connected. Assuming the graph does not satisfy (1) and (2),
are connected to the cycle consisting of
. WLOG, let
:
Again, to avoid (2), where
. Now to avoid (1), one of
.
Now it is clear that each vertex can go to any other vertex. This concludes our proof.
Say we try to avoid (3) so that WLOG . If we keep trying to avoid a "cycle",
and
which is a cycle.
Therefore, if there is any path , it will lead to a cycle and ultimately a valid path. The only way to avoid this is to have (1) or (2).
Consider (1):
WLOG, let have no arcs leading to it. Then all other vertices will have an arc directed toward them away from
. Therefore, one path can have only 1 unique vertex that has no arcs leading to it. There are 5 ways to choose the vertex and
ways for the remaining 6 arcs since they can be directed in any way. There are
paths for this condition.
Consider (2):
WLOG, let have all arcs leading to it. Similarly, all other vertices will have an arc that is directed away from them and points to
. Therefore, only one unique vertex can have all arcs leading to it. There are 5 ways to choose the vertex and
ways for the remaining arcs. There are also
paths for this condition.
However, we have overcounted paths that satisfy both (1) and (2). These paths will have one vertex that has all arcs leading to it and another that has all arcs directed away from it. There are ways to choose these 2 vertices, and the remaining
arcs each have 2 ways to be directed toward each other, so there are a total of
overlapping paths.
By PIE, the number of invalid cases is .
The total number of cases is since there are 10 edges and each can go 2 ways. By complementary counting, the number of valid paths is just
-Magnetoninja
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.