# 구체 수학 1장. 재귀적인 문제들

## 하노이의 탑

* 문제를 일반화해서 작은 사례들을 살펴보는 것이 유익하다.
* 원반 $n$개를 뤼카의 규칙하에서 다른 한 기둥으로 옮기는 데 필요한 최소한의 이동 횟수를 $T_n$이라고 하면 $T_0 = 0$이고, $T_1 = 1$, $T_2 = 3$임이 자명함.
* 크게 생각하는 쪽으로 관점을 바꿔보자:
  1. 작은 원반 $n - 1$개를 다른 기둥으로 옮긴다. ($T_{n - 1}$)
  1. 가장 큰 원반을 다른 기둥으로 옮긴다. ($T_1 = 1$)
  1. 다시 작은 원반 $n - 1$개를 가장 큰 원반 위로 옮긴다. ($T_{n - 1}$)
* 따라서 원반 $n$개의 이동 횟수는 $2T_{n - 1} + 1$을 넘지 않는다:

$$
T_n \leq 2T_{n - 1} + 1, n \gt 0 \text{에 대해.}
$$

* 등호가 아니라 부등호가 쓰인 이유는 탑을 옮기는 데 $2T{n - 1} + 1$번 이동이 충분하다는 것만을 증명했기 때문.
* 그러면 더 적은 수의 이동으로 탑을 옮길 수도 있을까?
  * 언젠가는 가장 큰 원반을 옮겨야 하는데, 그러기 위해서는 한 기둥에 $n - 1$개의 작은 원반들이 한 기둥에 쌓여 있어야 한다.
  * 작은 원반들을 한 기둥에 쌓기 위해서는 $T_{n - 1}$번 이동이 불가피하다.
  * 큰 원반을 마지막 기둥으로 옮긴 뒤에도 작은 원반들을 옮기려면 필연적으로 $T_{n - 1}$번 이동이 발생한다.
* 따라서 더 적은 수의 이동으로 탑을 옮길 수 없으며, 다음 식이 성립한다:

$$
\begin{aligned}
T_n &\geq 2T_{n - 1} + 1, n \gt 0 \text{에 대해.} \\
T_0 &= 0 \\
T_n &= 2T_{n - 1} + 1, n \gt 0 \text{에 대해. (1.1)}
\end{aligned}
$$

* 이러한 식을 점화식이라고 하며, 경계값(boundary value)와 방정식으로 구성된다.
* 닫힌 형식(closed form): 주어진 수량을 그 수량 자신을 이용하지 않고 표현하는 식. 이걸 구하면 $n$이 아무리 커도 빠르게 점화식의 해를 구할 수 있다. 작은 사례들을 살펴보자:

$$
\begin{aligned}
T_3 &= 2 \times 3 + 1 \\
T_4 &= 2 \times 7 + 1 \\
T_5 &= 2 \times 15 + 1 \\
T_6 &= 2 \times 31 + 1 \\
&\dots \\
T_n &= 2^n - 1, n \geq 0 \text{에 대해. (1.2)}
\end{aligned}
$$

* 수학적 귀납법에서 $n$의 가장 작은 값 $n_0$에 대해 증명하는 것을 기초 단계라고 부른다.
* 명제가 $n_0$에서 $n - 1$까지의 값들에 대해 이미 증명되었다는 가정하에 $n \gt n_0$에 대해 증명하는 것을 귀납 단계라고 부른다.
* $T_0 = 2^0 - 1 = 0$이므로 기초 단계는 자명하다.
* 식 (1.2)가 성립한다는 가정하에, 식 (1.1)과 식 (1.2)로부터 다음 등식을 얻을 수 있음:

$$
\begin{aligned}
T_n &= 2T_{n - 1} + 1 \\
&= 2(2^{n - 1} - 1) + 1 \\
&= 2^n - 1
\end{aligned}
$$

## 평면의 선들

* 칼로 피자를 $n$번 직선으로 자를 때 피자 조각이 최대 몇 개나 나올까?
* 즉, 평면에 놓인 $n$개의 직선으로 정의되는 영역의 최대 개수 $L_n$이 무엇일까?
* $L_0 = 1$, $L_1 = 2$, $L_2 = 4$임이 자명하다. 그렇다면 $L_n = 2^n$일까? 아니다. $L_3 = 4 + 3 = 7$이 가능하다.
* 하나의 새 선은 기존의 선 $n - 1$개와 많아야 $n - 1$개의 서로 다른 점에서 교차한다. 따라서 다음과 같은 점화식을 얻을 수 있다:

$$
\begin{aligned}
L_0 &= 1 \\
L_n &= L_{n - 1} + n, n \gt 0 \text{에 대해.}
\end{aligned}
$$

* 닫힌 형식을 구해보자. $1, 2, 4, 7, 11, 16, ...$에서는 패턴을 찾기 힘들다. 점화식을 펼치면 점화식을 더 잘 이해할 수 있다:

$$
\begin{aligned}
L_n &= L_{n - 1} + n \\
&= L_{n - 2} + (n - 1) + n \\
&= L_{n - 3} + (n - 2) + (n - 1) + n \\
&= L_0 + 1 + 2 + \dots + (n - 2) + (n - 1) + n \\
&= 1 + S_n, \text{여기서} S_n \text{은} 1 + 2 + 3 + \dots + (n - 1) + n.
\end{aligned}
$$

* 가우스가 9살 때 생각해낸 방법으로 해를 구할 수 있다. (이미 아르키메데스가 사용하긴 했다.)

$$
\begin{aligned}
2S_n &= [1 + 2 + 3 + \dots + (n - 1) + n] + [n + (n - 2) + (n - 1) + \dots + 2 + 1] \\
&= (n + 1) + (n + 1) + (n + 1) + \dots + (n + 1) + (n + 1) \\
&= n(n + 1), n \geq \text{에 대해.} \\
&\therefore L_n = {{n(n + 1)} \over 2} + 1, n \geq \text{에 대해.}
\end{aligned}
$$

## 요세푸스 문제

* 유대-로마 전쟁 도중 로마군은 41명의 유대인을 한 동굴에 가뒀다. 이들은 둥글게 둘러 앉아 돌아가며 매번 세번째 사람을 직접 처형하는 식으로 모두 자결하기로 했다. 요세푸스는 자신과 친구가 살아남으려면 원의 어디에 있어야 할지 계산했다.
* 문제를 변형해서 10명의 사람이 있고, 매번 두번째 사람이 죽는다고 하자. 그러면 $2, 4, 6, 8, 10, 3, 7, 1$ 순서이므로 5번 사람이 살아남는다. 즉, $J(10) = 5$다.
* $2n$명이 있을때 첫 바퀴 후에는 $1, 3, 5, 7, \dots, 2n - 3, 2n - 1$이 살아남는다. $J(2n) = 2J(n) - 1, n \geq 1 \text{에 대해.}$이다.
* 사람이 홀수인 경우엔? $3, 5, 7, 9, \dots, 2n - 1, 2n + 1$이다. 따라서 $J(2n + 1) = 2J(n) + 1, n \geq 1 \text{에 대해.}$