Difference between revisions of "2022 AIME II Problems/Problem 9"
(→Solution 3) |
(→Solution 3) |
||
Line 63: | Line 63: | ||
==Solution 3== | ==Solution 3== | ||
− | [[File:AIME 2022 II 9-min.png| | + | [[File:AIME 2022 II 9-min.png|350px|right]] |
Let some number of segments be constructed. We construct a new segment. We start from the straight line <math>l_B.</math> WLOG from point <math>B_3.</math> Segment will cross several existing segments (points <math>A,B,C,...</math>) and enter one of the points of the line <math>l_A (A_1).</math> | Let some number of segments be constructed. We construct a new segment. We start from the straight line <math>l_B.</math> WLOG from point <math>B_3.</math> Segment will cross several existing segments (points <math>A,B,C,...</math>) and enter one of the points of the line <math>l_A (A_1).</math> | ||
Line 74: | Line 74: | ||
Each point of intersection of two segments is determined <i><b> uniquely</b></i> by the choice of pairs of points on each line. | Each point of intersection of two segments is determined <i><b> uniquely</b></i> by the choice of pairs of points on each line. | ||
− | The number of such pairs is | + | The number of such pairs is <math> \dbinom{n}{2} \cdot \dbinom{m}{2}.</math> |
− | Exactly one segment comes to each of the n points of the line | + | |
− | Hence, the total number of bounded regions is N = | + | Exactly one segment comes to each of the <math>n</math> points of the line <math>l_A</math> from each of the <math>m</math> points of the line <math>l_B.</math> The total number of arrivals is equal to <math>mn.</math> |
+ | Hence, the total number of bounded regions is <math>N = \dbinom{n}{2} \cdot \dbinom{m}{2} + mn – 1.</math> | ||
We plug in <math>m=5, n=7</math>, we get the final answer of <math>\boxed{244}</math>. | We plug in <math>m=5, n=7</math>, we get the final answer of <math>\boxed{244}</math>. | ||
+ | |||
~vvsss (www.deoma-cmd.ru) | ~vvsss (www.deoma-cmd.ru) | ||
Revision as of 14:13, 1 June 2022
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 two 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
.
~DSAERF-CALMIT (https://binaryphi.site)
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
.
~vvsss (www.deoma-cmd.ru)
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.