평면에 직선 𝑛개를 그을 때 만들 수 있는 최대 영역 수

평면에 직선 $n$개를 그을 때 만들어지는 최대 영역 수를 하노이의 탑과 같은 흐름으로 정리한다. 핵심은 증가량이 등차수열 $(1,2,3,\dots)$이어서 삼각수가 자연스럽게 등장한다는 점이다.

1) 문제와 가정(일반 위치)

평면에 서로 다른 직선 $n$개.
일반 위치(general position) 가정
1. 평행 없음(아무 두 직선도 평행하지 않음)
2. 세 직선 이상이 한 점에서 만나지 않음
목표: 만들어지는 영역(면)의 최대 개수 $L_n$.

2) 분해와 점화식

직선을 하나씩 추가한다고 보면, 새 직선은 이전 $n-1$개의 직선을 서로 다른 $n-1$개의 점에서 만나고, 그 결과 $n$개의 구간으로 잘린다. 각 구간은 기존의 한 영역을 둘로 갈라 영역 수가 1씩 증가한다.

$$
\boxed{L_n = L_{n-1} + n,\qquad L_0 = 1.}
$$

3) 닫힌형(closed form)과 삼각수

점화식을 전개하면 증가량이 $1,2,3,\dots$로 누적되므로 삼각수 $T_n=\sum_{k=1}^n k=\dfrac{n(n+1)}{2}$가 바로 나타난다.

$$
\begin{aligned}
L_n
&= L_0 + \sum_{k=1}^{n} k
&= 1 + T_n
&= 1 + \frac{n(n+1)}{2}.
\end{aligned}
$$

즉,
$$
\boxed{L_n = T_n + 1 = \frac{n(n+1)}{2}+1 = \frac{n^2+n+2}{2}.}
$$

조합식 형태

삼각수 $T_n=\binom{n+1}{2}$이므로
$$
L_n = 1 + \binom{n+1}{2} = 1 + n + \binom{n}{2}.
$$
여기서 $\binom{n}{2}$는 교점의 개수, $n$은 “각 직선의 최상단(무한) 구간”의 기여로 해석할 수 있어 구조가 직관적이다.

4) 최대성의 엄밀 증명 스케치

4.1 강한 귀납(상한 달성)

기저 $n=0$: $L_0=1$.
귀납 가정: $n-1$개에서 최대는 $L_{n-1}$.
귀납 단계: 일반 위치에서 새 직선은 $n-1$개의 서로 다른 교점을 만들고 직선을 $n$구간으로 나눈다. 각 구간이 서로 다른 영역을 절단하므로 $L_n\le L_{n-1}+n$. 실제로 이런 배치를 만들 수 있으므로 상한이 달성되어 $L_n= L_{n-1}+n$.

4.2 오일러 공식(조합·그래프 관점)

직선 배치를 평면 그래프로 보면, 정점 $V=\binom{n}{2}$, 간선은 “한 직선이 구간 $n$개로 늘어난다”는 관찰로 누적 계산 가능. 오일러 공식 $V-E+F=1$ (무한 영역 포함, 연결 성분 1개)을 적용하면 같은 결과가 복원된다. 실전에서는 점화식이 가장 간결하다.

5) 일반화(평행·동점이 있을 때)

새로 추가하는 $i$번째 직선이 기존 직선들을 서로 다른 $t_i$개의 점에서 자르면, 그 직선 위 구간 수는 $t_i+1$이므로
$$
\boxed{L_n = 1 + \sum_{i=1}^{n} (t_i+1).}
$$

일반 위치: $t_i=i-1 \Rightarrow L_n=1+\sum_{i=1}^{n} i$.
평행이 생기거나(교점 감소), 세 직선 이상이 한 점에서 만나면(교점 합쳐짐) $t_i$가 작아져 최대치보다 적게 증가.

6) 성장률과 규모 감각

$$
L_n=\frac{n^2}{2}+O(n).
$$

영역 수는 이차적 증가. 하노이의 탑(지수 증가)과 대비하여 복잡도 감각 설명에 유용하다.

7) 구현

7.1 최대 영역 수(일반 위치)

def max_regions(n: int) -> int:
    return n * (n + 1) // 2 + 1

7.2 임의 배치(교점 수열이 주어질 때)

def regions_from_intersections(t_list):
    # t_list[i] = i번째(1-based)로 추가한 직선이 만드는 서로 다른 교점 수
    regions = 1
    for t in t_list:
        regions += (t + 1)
    return regions

예: 일반 위치 $n=5$라면 t_list=[0,1,2,3,4] → $1+\sum (t+1)=16$.

8) 드라이런(작은 $n$)

$n=0:\ L_0=1$
$n=1:\ L_1=L_0+1=2$
$n=2:\ L_2=L_1+2=4$
$n=3:\ L_3=L_2+3=7$
$n=4:\ L_4=L_3+4=11$

검증: 닫힌형 $L_n=\dfrac{n(n+1)}{2}+1$과 정확히 일치.

9) 자주 하는 오류 체크

증가량을 $n-1$로 잘못 기록(증가량은 새 직선 위 구간 수 $= n$).
동점(세 직선 이상 한 점 통과)·평행이 있는데 일반 위치 식을 그대로 적용.
“각 구간이 서로 다른 영역을 절단한다”는 사실을 누락해 증가량을 과·소평가.

10) 요약

분해 → $L_n=L_{n-1}+n,\ L_0=1$
닫힌형 $\displaystyle L_n=T_n+1=\frac{n(n+1)}{2}+1$
삼각수와의 직접 관계: 최대 영역 수 $=$ 삼각수 $+1$
일반화: 새 직선의 서로 다른 교점 수 $t_i$로 $L_n=1+\sum (t_i+1)$
성장률: 이차 $\sim \tfrac12 n^2$

저작자표시 비영리 변경금지 (새창열림)

붉은 각설탕