2022 AIME II Problems/Problem 9
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 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
.
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.