返回题库

HMMT 二月 2000 · POW 赛 · 第 19 题

HMMT February 2000 — POW Round — Problem 19

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. Supp ose we have n lines in a plane in general p osition, which means that none areparallel to each other and that no three of these lines in terse t at a single p oin t. Findthe number of regions that these lines divide the plane in to...
    (a) in a re ursiv e form.
    (b) in a nonre ursiv e form ula.
解析

nn 条一般位置直线将平面分割成的区域数。
(a) 递推形式： Rn=Rn−1+nR_{n} = R_{n-1} + n，R0=1R_{0}=1。
(b) 闭形式： Rn=1+∑k=1nk=n2+n+22R_{n} = 1 + \sum_{k=1}^{n} k = \frac{n^{2}+n+2}{2}。
Rn=n2+n+22\boxed{R_{n} = \frac{n^{2}+n+2}{2}}。

英文解析

nn lines in general position (no two parallel, no three concurrent). Find the number of regions formed.
(a) Recursive form: Adding the nn-th line, it intersects the previous n−1n-1 lines at n−1n-1 distinct points, dividing the new line into nn segments. Each segment splits an existing region, adding nn new regions.
Rn=Rn−1+n,R0=1.R_{n} = R_{n-1} + n, \quad R_{0} = 1.
(b) Closed form: Solving the recurrence:
Rn=1+∑k=1nk=1+n(n+1)2=n2+n+22.R_{n} = 1 + \sum_{k=1}^{n} k = 1 + \frac{n(n+1)}{2} = \frac{n^{2} + n + 2}{2}.
Rn=n2+n+22\boxed{R_{n} = \frac{n^{2}+n+2}{2}}.