Difference between revisions of "2022 AIME II Problems/Problem 9"
Magnetoninja (talk | contribs) (→Solution 5) |
Magnetoninja (talk | contribs) (→Solution 5) |
||
Line 104: | Line 104: | ||
Case 1: If a new point <math>P</math> is added to the right on a line when both lines have an equal amount of points. | Case 1: If a new point <math>P</math> is added to the right on a line when both lines have an equal amount of points. | ||
− | WLOG, let the point be on line <math>\ell_A</math>. We consider the complement, where new lines don't intersect other line segments. Simply observing, we see that the only line segments that don't intersect with the new lines are lines attached to some point that a new line does not pass through. Trivially, if we look at a series of points on line <math>\ell_B</math> from left to right and a line connects <math>P</math> to an arbitrary point, then the lines formed with that point and with remaining points on the left never intersect with the line with <math>P</math>. Let there be <math>s</math> points on lines <math>\ell_A</math> and <math>\ell_B</math> before <math>P</math> was added. For each of the <math>s</math> points on <math>\ell_B</math>, we subtract the total number of lines formed, which is <math>s^2</math>, not counting <math>P</math>. Considering all possible points on <math>\ell_B</math>, we get <math>(s^2-s)+(s^2-2s)\cdots(s^2-s^2)</math> total intersections. However, for each of the lines, there is one more bounded region than number of intersections, so we add <math>s</math>. Simplifying, we get <math>s^3-\sum_{i=1}^{s}{i}+s\Longrightarrow s(s^2-\sum_{i=1}^{s}{i}+1)</math>. Note that this is only a recursion formula to find the number of new regions added for a new point <math>P</math> added to <math>\ell_A</math>. | + | WLOG, let the point be on line <math>\ell_A</math>. We consider the complement, where new lines don't intersect other line segments. Simply observing, we see that the only line segments that don't intersect with the new lines are lines attached to some point that a new line does not pass through. Trivially, if we look at a series of points on line <math>\ell_B</math> from left to right and a line connects <math>P</math> to an arbitrary point, then the lines formed with that point and with remaining points on the left of that point never intersect with the line with <math>P</math>. Let there be <math>s</math> points on lines <math>\ell_A</math> and <math>\ell_B</math> before <math>P</math> was added. For each of the <math>s</math> points on <math>\ell_B</math>, we subtract the total number of lines formed, which is <math>s^2</math>, not counting <math>P</math>. Considering all possible points on <math>\ell_B</math>, we get <math>(s^2-s)+(s^2-2s)\cdots(s^2-s^2)</math> total intersections. However, for each of the lines, there is one more bounded region than number of intersections, so we add <math>s</math>. Simplifying, we get <math>s^3-\sum_{i=1}^{s}{i}+s\Longrightarrow s(s^2-\sum_{i=1}^{s}{i}+1)</math>. Note that this is only a recursion formula to find the number of new regions added for a new point <math>P</math> added to <math>\ell_A</math>. |
Case 2: If a new point <math>P</math> is added to the right of a line that has one less point than the other line. | Case 2: If a new point <math>P</math> is added to the right of a line that has one less point than the other line. |
Revision as of 17:20, 5 June 2023
Contents
Problem
Let and
be two distinct parallel lines. For positive integers
and
, distinct points
lie on
, and distinct points
lie on
. Additionally, when segments
are drawn for all
and
, no point strictly between
and
lies on more than 1 of the segments. Find the number of bounded regions into which this figure divides the plane when
and
. The figure shows that there are 8 regions when
and
Solution 1
We can use recursion to solve this problem:
1. Fix 7 points on , then put one point
on
. Now, introduce a function
that indicates the number of regions created, where x is the number of points on
. For example,
because there are 6 regions.
2. Now, put the second point on
. Join
and
will create
new regions (and we are not going to count them again), and split the existing regions. Let's focus on the spliting process: line segment formed between
and
intersect lines
,
, ...,
at
points
creating
regions (we already count one region at first), then
points
creating
regions (we already count one region at first), 4 points, etc. So, we have:
3. If you still need one step to understand this: and
will still create
new regions. Intersecting
at
points, creating
regions, etc. Thus, we have:
Yes, you might already notice that:
5. (Finally) we have , and
. Therefore, the answer is
.
Note: we could deduce a general formula of this recursion: , where
is the number of points on
Solution 2
We want to derive a general function that indicates the number of bounded regions. Observing symmetry, we know this is a symmetric function about
and
. Now let's focus on
, which is the difference caused by adding one point to the existing
points of line
. This new point, call it #m, when connected to point #1 on
, crosses
lines, thus making additional
bounded regions; when connected to point #2 on
, it crosses
lines, thus making additional
bounded regions; etc. By simple algebra/recursion methods, we see
Notice . Not very difficult to figure out:
The fact that makes us more confident about the formula. Now plug in
, we get the final answer of
.
Solution 3
Let some number of segments be constructed. We construct a new segment. We start from the straight line WLOG from point
Segment will cross several existing segments (points
) and enter one of the points of the line
Each of these points adds exactly 1 new bounded region (yellow bounded regions).
The exception is the only first segment which does not create any bounded region.
Thus, the number of bounded regions is
less than the number of points of intersection of the segments plus the number of points of arrival of the segments to
Each point of intersection of two segments is determined uniquely by the choice of pairs of points on each line.
The number of such pairs is
Exactly one segment comes to each of the points of the line
from each of the
points of the line
The total number of arrivals is equal to
Hence, the total number of bounded regions is
We plug in , we get the final answer of
.
vladimir.shelomovskii@gmail.com, vvsss
Solution 4 (Recursion with Detailed Explanation)
We use recursion for cases:
Case 1:
We add a new point on a line that already contains an equal number of points on lines and
, we call the number
. WLOG, let the point be on line
. Then, it will have to connect to all the points on line
. We observe that the number of new regions added for each line that connects the new point to some point on line
is one more than the number of times the line from the new point to a point on line
intersects another line formed by two arbitrary points on lines
and
which are not the new point. Therefore, we can focus on deriving a formula to find the number of intersections that will occur. We observe that the only way that a line chosen from two arbitrary points on lines
and
do not intersect with the line created from the new point to a point on line
is if the line is formed by a point on line
that is out of the "interval" in which the line created by the new point and the point on line
go through. Therefore, if the new point connects to the furthest point on line
, the number of lines that don't intersect will be the other lines formed by the point on line
that connect to another point on line
. Hence, the number of such lines is just
, since that point on line
can connect to any of the
points on line
which isn't the new point. Similarly, if the new point connects to the second furthest point on line
, two points on line
can form a line with any of the
points on line
. Generally, if the new point connects to the
th furthest point on line
, there will be
lines that don't intersect the line going through the new point and the
th furthest point on line
. We subtract the number of lines that never intersect with the line created by the new point and a point on line
from the total number of possible lines. We can do this since we know that a point will not be in the intersection of
or more lines.
Including all possible added regions connecting the new point to all the
points on line
, the equation for the total number of added regions across all possible lines can be modeled with
Case 2:
We add a point on line when there contains one more point on line
then line
. Following similar logic, each time that the new point connects to a point on line
, the number of lines that don't intersect with the newly formed line from the new point to line
is just the number of points on line
that are out of the "interval" of that line multiplied by the number of points on line
, which we will call
if
points are on line
. Then, we can find the number of added regions using the equation
.
For the base case , the number of regions is
. Therefore, all we need to do is plug in the values
for both formulas and apply
for the first formula to find the number of regions when there are
points on line
and
points on line
. Next, we use the formula
to find the number of regions when there are
points on line
and
points on line
after adding a point on line
again (This formula can be easily derived using the same method as above). After doing some calculations, we obtain the sum
Solution 5
When a new point is added to a line, the number of newly bounded regions it creates with each line segment will be one more than the number of intersection points the line makes with other lines.
Case 1: If a new point is added to the right on a line when both lines have an equal amount of points.
WLOG, let the point be on line . We consider the complement, where new lines don't intersect other line segments. Simply observing, we see that the only line segments that don't intersect with the new lines are lines attached to some point that a new line does not pass through. Trivially, if we look at a series of points on line
from left to right and a line connects
to an arbitrary point, then the lines formed with that point and with remaining points on the left of that point never intersect with the line with
. Let there be
points on lines
and
before
was added. For each of the
points on
, we subtract the total number of lines formed, which is
, not counting
. Considering all possible points on
, we get
total intersections. However, for each of the lines, there is one more bounded region than number of intersections, so we add
. Simplifying, we get
. Note that this is only a recursion formula to find the number of new regions added for a new point
added to
.
Case 2: If a new point is added to the right of a line that has one less point than the other line.
Continuing on case one, let this point be on line
. With similar reasoning, we see that the idea remains the same, except
lines are formed with
instead of just
lines. Once again, each line from
to a point on line
creates
non-intersecting lines for that point each point to its left. Subtracting from
lines and considering all possible lines created by
, we get
intersections. However, the number of newly bounded regions is the number of intersections plus the number of points on line
. Simplying, we get
newly bounded regions.
For the base case for both lines, there are
bounded regions. Next, we plug in
for both formulas and plug
for the first formula to find the number of regions when
and
. Notice that adding a final point on
is a variation of our Case 1. The only difference is for each of the
lines formed by
, there are
points that can form a non-intersecting line. Therefore, we are subtracting a factor of
lines instead of
lines from a total of
lines. However, the number of lines formed by
remains the same so we still add
at the end when considering intersection points. Thus, the recursive equation becomes
. Plugging
into this formula and adding the values we obtained from the other formulas, the final answer is
.
Video Solution
~MathProblemSolvingSkills.com
See Also
2022 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
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.