Difference between revisions of "2010 AMC 12A Problems/Problem 18"
m (→Further Explanation(for Solution 1)) |
|||
(5 intermediate revisions by 3 users not shown) | |||
Line 14: | Line 14: | ||
Hence the total number of paths is <math>2(1+64+784) = \boxed{1698}</math>. | Hence the total number of paths is <math>2(1+64+784) = \boxed{1698}</math>. | ||
== Solution 2== | == Solution 2== | ||
− | We will use the concept of complimentary counting. If you go in the square you have to go out by these labeled points(click the link) https://imgur.com/VysX4P0 and go out through the borders because if you didnt, you would touch another point in one of those points in the set of points in the link(Call it <math>S</math>). There is symmetry about <math>y=x</math>, so we only have to consider <math>(1,-1), (1,0)</math>, and <math>(1,1)</math>. <math>(1,1)</math> can go on the boundary in two ways, so we can only consider one case and multiply it by two. For <math>(1,0)</math> and <math>(1,-1)</math> we can just multiply by two. So we count paths from <math>(-4,4)</math> to each of these points, and then multiply that by the number of ways to get from the point one unit right of that to <math>(4,4)</math>, and all in all, we get the answer is <math>\dbinom{16}{8}-2[\dbinom{8}{3}\dbinom{7}{2}+\dbinom{9}{4}\dbinom{6}{2}+\dbinom{10}{5}\dbinom{5}{2}]=1698</math>, which is answer choice <math>\textbf{(D)}</math> | + | We will use the concept of complimentary counting. If you go in the square you have to go out by these labeled points(click the link) https://imgur.com/VysX4P0 and go out through the borders because if you didnt, you would touch another point in one of those points in the set of points in the link(Call it <math>S</math>). There is symmetry about <math>y=x</math>, so we only have to consider <math>(1,-1), (1,0)</math>, and <math>(1,1)</math>. <math>(1,1)</math> can go on the boundary in two ways, so we can only consider one case and multiply it by two. For <math>(1,0)</math> and <math>(1,-1)</math> we can just multiply by two. So we count paths from <math>(-4,4)</math> to each of these points, and then multiply that by the number of ways to get from the point one unit right of that to <math>(4,4)</math>, and all in all, we get the answer is <math>\dbinom{16}{8}-2\left[\dbinom{8}{3}\dbinom{7}{2}+\dbinom{9}{4}\dbinom{6}{2}+\dbinom{10}{5}\dbinom{5}{2}\right]=1698</math>, which is answer choice <math>\textbf{(D)}</math> |
-vsamc | -vsamc | ||
Note: Sorry if this was rushed. | Note: Sorry if this was rushed. | ||
+ | |||
+ | ==Further Explanation(for Solution 1)== | ||
+ | As stated in the solution, there are <math>6</math> points along the line <math>y=-x</math> that constitute a sort of "boundary". Once the ant reaches one of these <math>6</math> points, it is exactly halfway to <math>(4, 4)</math>. Also notice that the ant will only cross one of the <math>6</math> points during any one of its paths. Therefore we can divide the problem into <math>3</math> cases, focusing on <math>1</math> quadrant; then multiplying the sum by <math>2</math> to get the total (because there is symmetry). | ||
+ | |||
+ | |||
+ | For the sake of this explanation, we will focus on the fourth quadrant (it really doesn't matter which quadrant because, again the layout is symmetrical) The three cases are when the ant crosses <math>(4, -4), (3, -3),</math> and <math>(2, -2)</math>. | ||
+ | |||
+ | |||
+ | For each of the cases, notice that the path the ant takes can be expressed as a sequence of steps, such as: | ||
+ | |||
+ | |||
+ | right, right, up, right,..., etc. | ||
+ | |||
+ | |||
+ | Also notice that there are always <math>8</math> steps per sequence (if there were more or less steps, the ant would be breaking the conditions given in the problem). This means we can figure out the number of ways to get to a point based on the particular sequence of steps that denote each path. For example, there is only one way for the ant to pass through <math>(4, -4);</math> it MUST keep traveling right for all <math>8</math> steps. This seems fairly obvious; however, notice that this is equivalent to | ||
+ | |||
+ | |||
+ | <math>\binom{8}{0}</math> | ||
+ | |||
+ | |||
+ | Now we consider the number of ways to get from <math>(4, -4)</math> to <math>(4, 4)</math>. by symmetry, there is only <math>1</math> such way. So the number of paths containing <math>(4, -4)</math> is <math>1^2,</math> or <math>1</math>. | ||
+ | |||
+ | |||
+ | Moving on to the next case, we see that the ant MUST travel right exactly <math>7</math> times and up exactly once. So each sequence of this type will have <math>7</math> "right"s and <math>1</math> "up". So, the total number of paths that go through <math>(3, -3)</math> is equivalent to the number of ways to arrange <math>1</math> "up" into <math>8</math> spots. This is | ||
+ | |||
+ | |||
+ | <math>\binom{8}{1} = 8</math> | ||
+ | |||
+ | |||
+ | Similarly to the first case, we square this value to account for the second half of the journey: <math>8^2 = 64</math>. | ||
+ | |||
+ | |||
+ | Finally, for the third case (ant passes through <math>(2, -2)</math>) the ant must travel right exactly <math>6</math> times and up exactly <math>2</math> times. This is equivalent to the number of ways to arrange <math>2</math> "ups" in a sequence of <math>8</math> movements, or | ||
+ | |||
+ | |||
+ | <math>\binom{8}{2} = 28</math> | ||
+ | |||
+ | |||
+ | Again, we square <math>28</math>: <math>28^2 = 784</math>. Adding up all of these cases we get | ||
+ | |||
+ | |||
+ | <math>1+64+784 = 849</math> | ||
+ | |||
+ | |||
+ | paths through the fourth quadrant. Doubling this number to account for the paths through the second quadrant, we have | ||
+ | |||
+ | |||
+ | <math>849*2=1698 \Rightarrow \boxed{\text{D}}</math>. | ||
+ | |||
+ | |||
+ | For all the notation geeks out there, the solution can be expressed as such: | ||
+ | |||
+ | |||
+ | <math>2\sum_{k=0}^2 \binom{8}{k}^2</math> | ||
+ | |||
== See also == | == See also == | ||
{{AMC12 box|year=2010|num-b=17|num-a=19|ab=A}} | {{AMC12 box|year=2010|num-b=17|num-a=19|ab=A}} |
Latest revision as of 01:40, 2 February 2021
Problem
A 16-step path is to go from to
with each step increasing either the
-coordinate or the
-coordinate by 1. How many such paths stay outside or on the boundary of the square
,
at each step?
Solution 1
Each path must go through either the second or the fourth quadrant.
Each path that goes through the second quadrant must pass through exactly one of the points ,
, and
.
There is path of the first kind,
paths of the second kind, and
paths of the third type.
Each path that goes through the fourth quadrant must pass through exactly one of the points
,
, and
.
Again, there is
path of the first kind,
paths of the second kind, and
paths of the third type.
Hence the total number of paths is .
Solution 2
We will use the concept of complimentary counting. If you go in the square you have to go out by these labeled points(click the link) https://imgur.com/VysX4P0 and go out through the borders because if you didnt, you would touch another point in one of those points in the set of points in the link(Call it ). There is symmetry about
, so we only have to consider
, and
.
can go on the boundary in two ways, so we can only consider one case and multiply it by two. For
and
we can just multiply by two. So we count paths from
to each of these points, and then multiply that by the number of ways to get from the point one unit right of that to
, and all in all, we get the answer is
, which is answer choice
-vsamc
Note: Sorry if this was rushed.
Further Explanation(for Solution 1)
As stated in the solution, there are points along the line
that constitute a sort of "boundary". Once the ant reaches one of these
points, it is exactly halfway to
. Also notice that the ant will only cross one of the
points during any one of its paths. Therefore we can divide the problem into
cases, focusing on
quadrant; then multiplying the sum by
to get the total (because there is symmetry).
For the sake of this explanation, we will focus on the fourth quadrant (it really doesn't matter which quadrant because, again the layout is symmetrical) The three cases are when the ant crosses and
.
For each of the cases, notice that the path the ant takes can be expressed as a sequence of steps, such as:
right, right, up, right,..., etc.
Also notice that there are always steps per sequence (if there were more or less steps, the ant would be breaking the conditions given in the problem). This means we can figure out the number of ways to get to a point based on the particular sequence of steps that denote each path. For example, there is only one way for the ant to pass through
it MUST keep traveling right for all
steps. This seems fairly obvious; however, notice that this is equivalent to
Now we consider the number of ways to get from to
. by symmetry, there is only
such way. So the number of paths containing
is
or
.
Moving on to the next case, we see that the ant MUST travel right exactly times and up exactly once. So each sequence of this type will have
"right"s and
"up". So, the total number of paths that go through
is equivalent to the number of ways to arrange
"up" into
spots. This is
Similarly to the first case, we square this value to account for the second half of the journey: .
Finally, for the third case (ant passes through ) the ant must travel right exactly
times and up exactly
times. This is equivalent to the number of ways to arrange
"ups" in a sequence of
movements, or
Again, we square :
. Adding up all of these cases we get
paths through the fourth quadrant. Doubling this number to account for the paths through the second quadrant, we have
.
For all the notation geeks out there, the solution can be expressed as such:
See also
2010 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 17 |
Followed by Problem 19 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.