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