수학적 귀납법

(9/30 초판)

(9/30 ~ 10/10 PDF 연습 문제 17/22개 해결. 나머지는 시험 끝나고 시작할 것 같습니다.)

induction.pdf

(자료 출처는 이 사이트 내부 어딘가. 난 혜아한테 받아서 잘 모른다)

수학적 귀납법이란?

어떠한 명제 $P(1), P(2), P(3), \cdots$ 가 다음 두 성질을 만족한다고 하자. 

 * (기저 조건) $P(1)$ 이 참이다.

 * (귀납 조건) $n \geq 1$ 일 때, $P(1), P(2), \cdots P(n)$이 참이면, $P(n+1)$이 참이다. 

그렇다면 $P(1), P(2), P(3), \cdots$가 모두 참이다.

왜?

사실 위에 적은 수학적 귀납법을 "강한 수학적 귀납법" 이라고 부르고, 조금 더 약한 폼의 수학적 귀납법을 "수학적 귀납법" 이라 한다. 진짜 "수학적 귀납법"은

 * (기저 조건) $P(1)$ 이 참이다.

 * (귀납 조건) $n \geq 1$ 일 때, $P(n)$이 참이면, $P(n+1)$ 이 참이다. 

보다시피 강한 수학적 귀납법보다 약한 조건이다 (가정할 수 있는 것이 적으니까). 고로 연습 문제에서 내가 "수학적 귀납법" 이라 하면 강한 수학적 귀납법을 뜻한다.

수학적 귀납법이 그냥 참은 아니고, 다음과 같은 공리를 가정해야 참이다. 

 * (Well-ordering 성질) 자연수 집합의 임의의 부분집합은 최솟값을 가진다.

이 공리를 가정하면, 수학적 귀납법 / 강한 수학적 귀납법 / Well-ordering 성질이 모두 필요 충분 조건임을 보일 수 있다.

Well-ordering 성질 -> 강한 수학적 귀납법

귀류법으로 증명한다. 다음과 같은 명제 $S(n)$이 있다고 하자. 

* (기저 조건) $S(1)$ 이 참이다.

* (귀납 조건) 모든 $n \in N$에 대해서, $S(1), S(2), \cdots, S(n)$ 이 전부 참이면, $S(n+1)$이 참이다.

* $S(n)$ 이 거짓인 $n \in N$ 이 존재한다.

$X = \{ n \in N|S(n)\text{ 이 거짓}\}$ 이라 하자. Well-ordering 성질에 의해서 최솟값 $m$이 존재한다. $m = 1$ 이면 기저 조건과 모순이다. 아니면, $S(1), S(2), \cdots, S(m-1)$ 이 모두 참이지만 $S(m)$ 이 거짓이니 귀납 조건과 모순이다. 

고로, well-ordering 성질이 가정되었을 때 강한 수학적 귀납법이 성립한다. 

강한 수학적 귀납법 -> 수학적 귀납법

다음을 만족하는 명제 $S(n)$ 을 생각하자. 

* (기저 조건) $S(1)$ 이 참이다. 

* (귀납 조건) 모든 $n \in N$에 대해서, $S(n)$이 참이면, $S(n+1)$이 참이다.

그렇다면, 자명히

* (기저 조건) $S(1)$ 이 참이다.

* (귀납 조건) 모든 $n \in N$에 대해서, $S(1), S(2), \cdots, S(n)$ 이 전부 참이면, $S(n+1)$이 참이다.

가 성립한다. $S(n)$만 참이어도 참이 되는데, 나머지까지 참이면 땡큐다. 

이 때, 강한 수학적 귀납법에 의해서, 모든 $S(n)$이 참이다. 고로, 강한 수학적 귀납법을 가정했을 때 수학적 귀납법이 성립한다. 

수학적 귀납법 -> Well-ordering 성질

수학적 귀납법으로, 모든 자연수 $n$에 대해서, $n$ 이하의 원소를 가지는 부분집합은 최솟값을 가짐을 증명한다. 

* (기저 조건) 1 이하의 원소를 가지는 부분집합은, 최솟값 1을 가진다. 

* (귀납 조건) $n \geq 1$일 때, 어떠한 부분집합이 $n$ 이하의 수를 가지면 최솟값을 가진다. 그렇지 않다면, 집합은 $n$ 이하의 수는 없지만, $n+1$이 있다. 이 때는 $n+1$이 최솟값이다.  

임의의 공집합이 아닌 부분 집합 $X \subset N$에서 우리는 자연수 $n \in X$을 뽑을 수 있다. $X$는 $n$ 이하의 원소를 가지니, $X$는 최솟값을 가진다. 

수학적 귀납법은, Well-ordering 성질을 만족하는 모든 Well-ordered set에 대해서 잘 성립한다. 즉, 굳이 자연수가 아니더라도 정렬할 수 있는 모든 집합에 대해서 성립한다. 정렬한 다음에 각각의 원소에 자연수를 순서대로 배정하고, 그 자연수에 대해서 수학적 귀납법을 사용한다고 생각하자.

PDF 연습 문제 (16/22)

(틀리면 말해 주세요.. 틀릴 수 있어요 ㅠㅠ)

문제 1

사실 IOI 2014 연습 세션에 나왔던 문제이다.. 일단 다음 명제를 증명하자.

Lemma. $n \geq 1$ 에 대해, $2^n * 2^n$ 격자 중 상하좌우 한 쪽 사분면 (크기 $2^{n-1} * 2^{n-1}$) 이 잘린 도형을 ㄱ자 모양 타일로 채울 수 있다.

증명 : $n = 1$ 기저 조건은 자명하다. 빈 공간에 ㄱ자 하나를 넣으면 쏙 들어간다.

$n \geq 2$일 때, 일반성을 잃지 않고 좌상단 사분면이 잘렸다고 하면, 나머지를 다음과 같이 나눌 수 있다.

##AA

##DA

BDDC

BBCC

귀납 가정에 의해서 각 A, B, C, D를 채울 수 있으니 $n$에서도 명제가 성립한다. 고로 모든 자연수 $n$에 대해서 성립한다. 이제 문제의 명제를 증명하자. 

* (기저 조건) $n = 0$일 때는 채울 곳이 없다.

* (귀납 조건) $n \geq 1$일 때, 상하좌우 한 쪽 사분면에는 빠진 칸이 있을 것이다. 이 쪽 사분면을 제외한 부분은 위 Lemma에 의해서 채울 수 있고, 이 쪽 사분면은 $n-1$에서의 귀납 가정에 의해 채울 수 있다.

고로, 수학적 귀납법에 의해서 증명이 끝난다.

문제 2

$n \geq 2$일 때 명제를 증명하자.

* (기저 조건) $n = 2$이면 그냥 2를 쓰면 된다.

* (귀납 조건) $n$이 소수일 때는, 자명히 소수 하나의 곱으로 쓸 수 있다. $n$이 소수가 아닐 때는, 2 이상 $n-1$ 이하의 $n$의 약수를 찾을 수 있다. 이 약수를 $d$라 하자. $d, n/d$ 모두 $n$ 미만 $2$ 이상이기에, 이들은 귀납 가정에 의해서 소수들의 곱으로 쓸 수 있으니, 둘을 붙여주면 $n$을 소수의 곱으로 쓸 수 있다. 

고로, 수학적 귀납법에 의해서 증명이 끝난다. 

문제 3

왜 3번에 있는지는 잘 모르겠지만 아무튼 아주 재미있는 문제이다. 편의상 칸이 아니라 점이라고 부른다. 

* (기저 조건) $n = 1$이면 돌이 하나밖에 없고, 곧 없어지니 자명하다.

* (귀납 조건) $n$개의 검은 점이 2차원 평면의 격자점에 있다고 생각하고, 이들 중 최소 $x$좌표를 가지는 점을 $p$, 최소 $y$좌표를 가지는 점을 $q$라고 하자. $x_i > x_p$ 를 만족하는 모든 점들은 $n-1$초 후 사라진다. $x_p$를 만족하는 하나 이상의 점들을 제거하면, $n-1$개 이하의 점들이 남기 때문이다. 이들의 왼쪽 ($x = x_p$) 에 어떤 것이 생겨도 그 상황은 바뀌지 않는다. 고로 귀납 가정을 적용할 수 있다. 마찬가지로, $y_i > y_p$ 를 만족하는 모든 점들은 $n-1$초 후 사라져 있다. 이렇게 했을 때, $n-1$초 이후 검은 점이 있을 수 있는 위치는 오직 $(x_p, y_p)$ 단 한 격자 뿐이다. 이 격자가 비어 있건 말건 자명히 1초 후에는 비게 될 것이다. 고로 $n$초 뒤에 격자에 검은 점은 없다.

문제 4

* (기저 조건) $n = 0$이면 $\binom{0}{0} x^0 = 1$ 이라 그냥 된다. 

* (귀납 조건) $n \geq 1$이면, 귀납 가정에 의해서 $(x+1)^{n-1} = \sum_{k = 0}^{n-1}{\binom{n-1}{k}x^k}$ 이다. 양변에 $x+1$을 곱해주면 $(x+1)^n = \sum_{k = 0}^{n-1}{\binom{n-1}{k}(x^k + x^{k+1})}$ 이다. 더 잘 써보면 $\binom{n-1}{0}x^0 + \sum_{k = 1}^{n-1}{(\binom{n-1}{k} + \binom{n-1}{k-1})x^{k}} + \binom{n-1}{n-1}x^n$이다. $\binom{n}{0} =  \binom{n}{n} = \binom{n-1}{0} = \binom{n-1}{n-1} = 1$ 이고 $\binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k}$ 니까 결국 저 식은 $\sum_{k = 0}^{n}{\binom{n}{k}x^k}$이 된다. 

문제 5

* (기저 조건) $n = 1$ 이면 $|A_1| = |A_1|$ 이다.

* (귀납 조건) $n \geq 2$ 일 때, $|\bigcup_{k=1}^{n}{A_i}| = |\bigcup_{k=1}^{n-1}{A_i}| + |A_n| - |(\bigcup_{k=1}^{n-1}{A_i})\bigcap{A_n}|$ 이다. 여기서 식 정리를 계속 하면 된다. 수식으로 쓰기 힘들다.. 하..

$|\bigcup_{k=1}^{n-1}{A_i}| + |A_n| - |(\bigcup_{k=1}^{n-1}{A_i})\bigcap{A_n}|$

= $|\bigcup_{k=1}^{n-1}{A_i}| + |A_n| - |(\bigcup_{k=1}^{n-1}{(A_i\bigcap{A_n})})|$

= $|\bigcup_{k=1}^{n-1}{A_i}| + |A_n| - \sum_{k=1}^{n-1}{(-1)^{k-1}\sum_{I\subset\{1, 2, \cdots, n\}, \{n\}\in I. |I| = k+1}{|\bigcap_{i\in I}{A_i}|}}$

= $|\bigcup_{k=1}^{n-1}{A_i}| + |A_n| + \sum_{k=2}^{n}{(-1)^{k-1}\sum_{I\subset\{1, 2, \cdots, n\}, \{n\}\in I. |I| = k}{|\bigcap_{i\in I}{A_i}|}}$

= $|\bigcup_{k=1}^{n-1}{A_i}| + \sum_{k=1}^{n}{(-1)^{k-1}\sum_{I\subset\{1, 2, \cdots, n\}, \{n\}\in I. |I| = k}{|\bigcap_{i\in I}{A_i}|}}$

= $\sum_{k=1}^{n}{(-1)^{k-1}\sum_{I\subset\{1, 2, \cdots, n\}, \{n\}\notin I. |I| = k}{|\bigcap_{i\in I}{A_i}|}} + \sum_{k=1}^{n}{(-1)^{k-1}\sum_{I\subset\{1, 2, \cdots, n\}, \{n\}\in I. |I| = k}{|\bigcap_{i\in I}{A_i}|}}$

= $\sum_{k=1}^{n}{(-1)^{k-1}\sum_{I\subset\{1, 2, \cdots, n\}, |I| = k}{|\bigcap_{i\in I}{A_i}|}}$

문제 6

* (기저 조건) $n = 1$이면 자명하다.

* (귀납 조건) $n \geq 2$ 일 때, 두 가지 경우가 있다.

1. 짝수일 때 : 귀납 가정에 의해서 $\frac{n}{2}$일 때 만족하니, $\frac{a_1+a_2+\cdots +a_{n/2}}{n} + \frac{a_{n/2+1}+a_{n/2+2}+\cdots +a_n}{n}\geq \frac{1}{2}\sqrt[n/2]{a_1a_2\cdots a_{n/2}} + \frac{1}{2}\sqrt[n/2]{a_{n/2+1}a_{n/2+2}\cdots a_{n}}$ 을 만족한다. 

한편, $P, Q \geq 0$일 때 $\frac{P + Q}{2} \geq \sqrt{PQ}$인데, 양변을 제곱해서 빼면 $(P-Q)^2 = 0$이기 때문이다. $a_1, a_2, \cdots, a_n > 0$이니 $P, Q \geq 0$을 자명히 만족하고, 이어 붙이면 $\frac{a_1+a_2+\cdots +a_{n}}{n} \geq \sqrt[n]{a_1a_2\cdots a_{n}}$이 된다. 

2. 홀수일 때 : 귀납 가정에 의해서 $\frac{n+1}{2}$일 때 만족하니, 짝수일 때와 똑같은 과정으로 $n+1$에 대해서 식이 만족함을 알 수 있다. $a_{n+1} = \frac{a_1+a_2+\cdots +a_n}{n}$ 이라 두면, 

$\frac{a_1+a_2+\cdots +a_{n+1}}{n+1} \geq \sqrt[n+1]{a_1a_2\cdots a_{n+1}}$

$(\frac{a_1+a_2+\cdots +a_{n+1}}{n+1})^{n+1} \geq a_1a_2\cdots a_{n+1}$

$(\frac{a_1+a_2+\cdots +a_{n}}{n})^{n+1} \geq a_1a_2\cdots a_n\frac{a_1+a_2+\cdots +a_n}{n}$

$(\frac{a_1+a_2+\cdots +a_{n}}{n})^{n} \geq a_1a_2\cdots a_n$

$\frac{a_1+a_2+\cdots +a_{n}}{n} \geq \sqrt[n]{a_1a_2\cdots a_{n}}$

문제 7

먼저 $G$는 연결 그래프다. 그렇지 않다고 치면, $\frac{n}{2}$ 이하 크기의 컴포넌트가 존재하고, 이 컴포넌트에 속하는 정점의 degree는 절대 $\frac{n}{2}$ 이상이 될 수 없기 때문이다. 

$G$의 최장 경로를 $P = \{x_0, x_1, \cdots, x_k\}$라 하자. 최장 경로이기 때문에, $x_0$의 모든 인접한 정점과, $x_k$의 모든 인접한 정점은 $P$에 존재한다. 그렇지 않다면 길이를 하나 늘려줄 수 있기 때문이다. 또한, $x_0 - x_{i+1}$, $x_i - x_k$를 잇는 에지가 둘다 존재하는 $i$가 $0 \leq i \leq k-1$ 에서 항상 존재한다. 만약 존재하지 않는다면, 모든 $0 \leq i \leq k-1$에 대해서 $x_0 - x_{i+1}$, $x_i - x_k$를 잇는 에지가 많아야 하나만 존재할 것이고, 고로 이들의 개수는 최대 $k$개 ($k \leq n-1$) 인데, $x_0$과 $x_k$의 차수를 더하면 $n$ 이상이기 때문이다. 

저러한 에지가 존재함은, 우리가 $C = \{x_0, x_{i+1}, x_{i+2}, \cdots, x_{k-1}, x_k, x_i, x_{i-1}, x_{i-2}, \cdots, x_1, x_0\}$ 과 같은 사이클을 찾을 수 있음을 뜻한다. 이 사이클은 해밀턴 사이클이다. 만약 그렇지 않다면, 그래프가 연결이기 때문에 사이클 안과 사이클 밖을 잇는 $e = \{v, x_j\}$ 가 존재할 것이다. $x_j$의 사이클 왼쪽 / 오른쪽 끝을 자르고, 거기에 $v$를 붙여주면, 원래 찾은 최장 경로보다 정점의 개수가 1개 늘어난다. 고로 가정에 모순이고, $C$는 해밀턴 사이클이다. 

문제 8

정점의 개수에 대해서 수학적 귀납법을 사용한다. 

* (기저 조건) 단순 그래프가 $|V(G)| = 1$ 이면 $|E(G)| = 0$을 만족해야 함으로 참이다.

* (귀납 조건) $|V(G)| \geq 2$ 을 가정하자. 만약에 에지가 없다면 그래프에서 연결되지 않은 두 서로 다른 정점 $v, w \in V(G)$를 찾을 수 있으니, 이 그래프에는 최소 하나의 에지가 존재한다. 이 에지를 $e = {v, w}$라고 하자. 

만약 에지를 제거한 이후에 그래프가 연결되어 있다면, $v$에서 $w$로 가는 경로가 존재함을 알 수 있다. 이 경로의 끝에 $e$를 붙이면 $G$에 사이클이 존재하니 모순이고, 고로 에지를 제거한 이후에 그래프는 연결되어 있지 않다. 또한, 에지를 제거한 이후 그래프는 3개 이상의 컴포넌트로 나뉘지 않는다. 만약 그렇다면, 3개 이상의 컴포넌트를 에지 하나로 하나의 컴포넌트로 묶을 수 있다는 뜻이 되니 모순이다. 고로, 에지를 제거한 이후 그래프는 정확히 2개의 컴포넌트로 나뉘어진다.

각각의 컴포넌트는 정의상 연결되어 있으며, 사이클을 가지지 않는다. 사이클을 가진다면, $G$에도 사이클이 있기 때문이다. 즉, 각각의 컴포넌트는 수형도이다. 두 컴포넌트를 $A, B$라 하자. 컴포넌트의 정의 상 정점의 개수가 1개 이상이니, $1 \leq |V(A)|, |V(B)| < |V(G)|, |V(A)| + |V(B)| = |V(G)|$ 임을 알 수 있다. 귀납 가정에 의하여, 이 컴포넌트들의 에지 개수 합은 $|V(A)| + |V(B)| - 2$ 이다. 여기에 에지 $e$를 더하면, 원래 그래프의 에지 개수가 $|V(G)| - 1$임을 알 수 있다. 고로, $|E(G)| = |V(G)| - 1$이다. 

문제 9

어떠한 수형도에 차수가 1 이하인 정점이 없다고 해 보자. 모든 정점의 차수는 2 이상이니, 차수의 합은 $2|V(G)|$ 이상일 것이다. 에지의 개수는 차수의 합의 절반이니, $|E(G)| \geq |V(G)|$ 임을 알 수 있다. 하지만, 문제 8의 결과에 의해 수형도는 $|E(G)| = |V(G)| - 1$ 을 만족하니, 모순이다. 고로 어떠한 수형도에는 차수가 1 이하인 정점이 항상 존재한다. 

문제 10

먼저 그래프가 연결되어 있다고 가정한다. 그래프가 연결되어 있을 때 명제가 참이면, 연결되지 않은 그래프를 연결 컴포넌트로 나눠서, 각 연결 컴포넌트를 A / B 색으로 칠한 후 합쳐도 두 쪽을 잇는 선이 생기지 않는다. 고로 연결된 상황에서 증명하면, 그래프가 연결되어 있지 않을 때도 명제가 참이 된다.

이제 홀수 길이 회로가 없는 연결 그래프에서 색칠 방법이 존재함을 간선 개수에 대한 수학적 귀납법으로 보인다.개이다. 그냥 A로 칠하고 끝내면 된다.

* (기저 조건) $|E(G)| = 0$이면, 연결 그래프이니 $|V(G)| = 1$이다. 그냥 그 정점을 A로 칠하고 끝내면 된다.

* (귀납 조건) $|E(G)| \geq 1$일 때, $|V(G)| \geq 2$임을 확인하자. 두 가지 케이스가 있다.

* Case 1. $G$가 트리(수형도)일 때 : 문제 9에 의해서 트리에는 차수 1 이하인 정점이 존재한다. 더 나아가서, 정점의 개수가 2 이상일 때 차수 0인 정점이 존재하면 연결되었다는 가정에 모순이니, 정확히 차수 1인 정점이 존재한다. 귀납 가정에 의해서, 이 정점 $v$과 이 정점이 연결된 간선 $e = \{v, u\}$을 제거한 그래프에서 색칠 방법을 찾을 수 있다. $v$에는 $u$에 적혀있는 색을 반대로 적어주면 된다. 

* Case 2. $G$가 트리가 아니라면 : 정의에 의해 $G$에는 회로가 존재한다. 회로의 임의의 간선 $e = \{u, v\}$을 제거하자. 회로에서 간선을 제거했기 때문에 연결성은 바뀌지 않고, 귀납 가정에 의해서 간선을 제거한 그래프의 색칠 방법을 찾을 수 있다. 만약 여기서 제거한 간선을 추가했을 때, 이 간선이 똑같은 색을 잇는다고 생각해 보자. $G$는 연결 그래프이니 $u, v$를 잇는 경로가 존재하고, $u$와 $v$의 색이 같으니 경로의 길이는 짝수이다. 여기에 $e$를 더하면 홀수 회로를 찾을 수 있고, 가정에 모순이다. 고로 제거한 간선을 추가했을 때 간선은 항상 똑같은 색을 잇지 않는다.

문제 11

Lemma 1. 모든 연결 그래프에는 절점이 아닌 정점이 존재한다.

Proof : $|V(G)| \leq 2$일 때는 모든 정점이 절점이 아니니 자명하다. $|V(G)| \geq 3$일 때 잡은 임의의 정점 $v$가 절점이라고 하자. $v$를 제거하면 그래프는 여러 컴포넌트로 나뉠 것이고, 이 중 최소 크기의 컴포넌트를 $minComp(v)$라 하자. $minComp(v)$ 에 속하며 $v$와 인접한 정점 $w$를 보았을 때, $w$는 절점이 아니거나, $|minComp(w)| < |minComp(v)|$를 만족한다. 즉, $v$가 절점이라면, $|minComp(v)|$를 1 이상 줄이거나 절점이 아닌 정점 $w$를 찾을 수 있다. $|minComp(v)|$는 유한하기 때문에 $G$에서 절점 아닌 정점을 찾을 수 있다.

이제 수학적 귀납법으로, 항상 그러한 두 정점을 고를 수 있음을 증명한다. 정점의 개수 $n$에 대해 귀납법을 사용한다. $n \geq 2$일 때부터 문제가 정의됨에 유의하자.

* (기저 조건) $n = 2$일 경우, 에지가 0개거나 1개이고, 어느 상황에서도 현재 두 정점을 사용하면 된다. $n = 3$일 경우, 에지가 0개면 아무 두 정점, 1/2개면 길이 1/2의 path이니 path의 양 끝점, 3개면 아무 두 정점을 고르면 만족한다.

* (귀납 조건) $n \geq 4$이고 그래프가 연결되지 않았다면, 그래프는 여러 개의 연결 컴포넌트로 나뉜다. 이 중 크기가 2 이상인 것이 없다면, 아무 두 정점을 고르면 된다. 그렇지 않다면, 귀납 가정에 의해 크기 2 이상인 임의의 컴포넌트에서 그러한 두 정점을 고를 수 있으니, 답을 찾을 수 있다.

고로 $n \geq 4$이며 연결 그래프임을 가정한다. Lemma 1에 의해서 절점 아닌 정점 $p$를 고를 수 있고, 귀납 가정에 의해서 $G \setminus \{p\}$ 에서 그러한 두 정점 $u, v$를 찾을 수 있다. 만약, $p$가 $u, v$와 모두 연결되어 있거나, 모두 연결되어 있지 않으면 문제가 끝난다. 고로 일반성을 잃지 않고 $p$는 $u$와 연결되어 있지만 $v$와 연결되어 있지 않다고 하자. 이제 두 케이스를 생각한다.

* Case 1, $u, v$가 에지로 연결되어 있지 않다. $u, v$의 공통된 이웃들을 $N$, $p$의 이웃이며 $N$에 속하지 않는 정점들을 $X$, $u, v, p$ 모두에 인접하지 않은 나머지들을 $M$ 이라 부른다. 이 때 $n \geq 4$이며 연결 그래프이기 때문에 $|N| \geq 1$이다. 차근 차근 시작하면

1. 일단 $p$는 $N$에 있는 모든 정점들과 이웃하다. $x \in N$에 대해 p - u - x - v 라는 path를 생각해보자. 가정상 p - v, u - v는 안되니 p - x로 가는 에지가 있어야 한다.

2. 임의의 $x \in X, y \in N$에 대해 x - y를 잇는 간선이 존재한다. x - p - y - v라는 path에서 가정상 x - v, p - v가 안되기 때문이다.

3. 임의의 $x \in X, y \in M$에 대해 x - y를 잇는 간선이 존재하지 않는다. 하나라도 존재함을 가정하면, u - p - x - y라는 path가 생긴다. u - y, p - y, u - x 그 어떤 쪽으로도 에지를 이을 수 없다. 모순이다.

이제 문제를 해결해 보자.

* $|X| = 0$이면, $p, u$의 이웃이 모두 $N$이다.

* $|X| = 1$이면, $X = \{x\}$라 두자. $x, u$의 이웃이 모두 $N\cup\{x\}$으로 같다.

* $|X| \geq 2$이면, $X$의 induced subgraph에서 그러한 정점 두개를 찾을 수 있다. 이 정점들은 모두 $p, N$와 인접하고, $u, v, M$과 인접하지 않으므로, $X$에 이러한 정점들 더해줘도 여전히 정점 두개가 유지된다. 

고로 찾을 수 있다.

* Case 2. $u, v$가 에지로 연결되어 있다. 아까와 똑같이 $N, X, M$을 정의한다. 먼저 $X = \emptyset$이다. 만약 $w \in X$가 존재한다면, w - p - u - v라는 path를 찾을 수 있고, w - u, w - v, p - v 모두 불가능하기 때문이다. 또한, 이제 $N$을 $P, Q$로 가르자. $P$는 $N$에서 $p$랑 에지가 존재하는 정점의 집합이고, $Q$는 $N \setminus P$ 이다. 또 시작하면

1. 임의의 $x \in Q, y \in M$ 에 대해서 x - y를 잇는 간선은 존재하지 않는다. 존재한다고 가정하면, p - u - x - y라는 path가 생기는데, p - x, p - y, u - y 모두 가정에 모순이다. 

2. 임의의 $x \in P, y \in Q$에 대해서 x - y를 잇는 간선은 항상 존재한다. 존재하지 않다고 가정하면, p - x - v - y라는 path에서 x - y, p - v, p - y 모두 가정에 모순이다. 

이제 문제를 해결해 보자. 

* $|Q| = 0$이면, $p, v$가 답이 된다. 모두 $P \cup \{u\}$와 인접하다.

* $|Q| = 1$이면, $Q = \{q\}$라 하면 $v, q$가 답이 된다. 모두 $P \cup \{u\}$와 인접하다.

* $|Q| \geq 2$이면, $Q$의 induced subgraph에서 그러한 정점 두개를 찾을 수 있다. 이 정점들은 모두 $v, u, P$와 인접하고, $p, M$과 인접하지 않으므로, $Q$에 이러한 정점들 더해줘도 여전히 정점 두개가 유지된다. 

고로 찾을 수 있다.

난 이 풀이를 찾다가 멘탈이 나갈 뻔했는데, 실제 대회에는 뭔가 힌트가 있었고 힌트의 관찰을 사용하면 쉬운 접근이 있었던 거 같다. 지금 진짜 멘탈이 나가서 링크만 첨부한다. https://quadue.wordpress.com/2010/08/24/2010-kmo-4/

문제 12

문제 13

예전에 블로그에 포스팅한 적도 있는 재미있는 매칭 게임이다. $n$이 짝수거나 $m$이 짝수이면 첫번째 사람이 이기고, 아니면 두번째 사람이 이긴다.

먼저 $n, m$ 중 하나가 짝수일 때를 설명한다. 일반성을 잃지 않고 $n$이 짝수라고 하자. $1 \leq i \leq \frac{n}{2},1 \leq j \leq m$, 일 때, $(2i-1, j)$와 $(2i, j)$ 를 매칭시키면, 모든 바둑판의 위치가 짝을 가진다. 한 턴을 첫번째 / 두번째 사람이 움직인 이후라 정의하자. $i \geq 0$번의 턴 이후 게임이 끝나지 않았다면, 두 매칭된 위치 쌍은 1. 둘 다 방문 안되어 있거나 2. 둘 다 이미 방문되었거나 3. 한 쪽에 바둑돌이 있고 나머지 쪽이 방문되지 않았거나. 이 3가지 조건을 만족하게 할 수 있음을 증명한다.

* (기저 조건) $i = 0$일 때는 왼쪽 아래 쌍만 3번 상태고, 나머지는 다 1번 상태이다.  

* (귀납조건) $i \geq 0$일 때, 현재 바둑돌이 있는 위치가 3번 상태이니, 나머지 쪽을 방문시켜 상태를 2번으로 전환시킨다. 상대 플레이어가 어디로 움직이던간에, 그 위치는 1번 상태일 것이다. 3번 상태는 사라졌고, 2번 상태에는 올릴 수 없기 때문이다. 1번 상태의 짝에 바둑돌을 올리면 그 짝은 3번 상태가 되니, $i+1$번째 턴에서도 조건이 만족된다. 옮길 수 있는 곳이 없으면, 게임이 두번째 사람의 패배로 끝난다. 

바둑돌에 매칭된 쪽이 비어있다는 것은, 플레이어 1이 $i$번의 턴 이후 항상 할 것이 있음을 뜻한다. 총 위치가 $nm$개이니, 턴의 횟수는 유한하다. 고로 플레이어 1은 언제나 할 것이 있다.

$n, m$이 모두 홀수이면, 유사한 방법으로 해당 위치만 빼놓고 짝을 짓게 시킬 수 있다. 첫번째 사람이 어딘가로 움직인 즉시, 두 매칭된 위치 쌍은 1. 둘 다 방문 안되어 있거나 2. 둘 다 이미 방문되었거나 3. 한 쪽에 바둑돌이 있고 나머지 쪽이 방문되지 않았거나. 이 3가지 조건을 만족한다. 고로 아까 썼던 논리를 그대로 사용하면 두번째 사람이 이긴다.

문제 14

문제 15 / 문제 16

PDF에도 나와 있듯이 문제 15는 문제 16의 서술을 일상 용어로 바꾼 것이므로 생략한다. 이제부터는 다음과 같은 용어를 사용한다.

 * alternating path : 매칭에 속하지 않는 정점 $v \in A$에서 시작하여, 매칭 아닌 간선 - 매칭 간선 - 매칭 아닌 간선 .. 의 사용을 반복하는 경로. 

 * augmenting path : 매칭에 속하지 않는 정점 $v \in A$에서 시작하여 매칭에 속하지 않는 정점 $w \in B$에서 끝나는 alternating path. augmenting path가 존재한다면, 현재 매칭의 크기를 1 늘려줄 수 있음을 확인하자. A B-A B-A B-A B 와 같은 매칭을, A-B A-B A-B A-B 로 바꿔줄 수 있기 때문이다.

일단, 완벽 매칭이 존재할 경우 모든 부분집합 $X \subset A$에 대해 $|N(X)| \geq |X|$을 만족한다. $X$의 매칭 반대에 있는 정점들은 $X$의 이웃의 부분집합이기 때문이다. 고로, 우리는 그 역을 증명하는 데 집중할 것이다. Dietsel의 Graph Theory에 나온 세 증명 방법을 모두 서술한다. 

증명 1. $A$에 있는 모든 정점을 다음 알고리즘을 통해서 매칭시킬 수 있다. 현재 어떠한 정점 $v \in A$가 매칭을 찾지 못했다고 하자. $v$에서 alternating path로 도달할 수 있는 모든 $A$ 정점을 $A'$, $B$ 정점을 $B'$ 라 하자. $B'$ 중 매칭에 속하지 않은 정점이 존재하면, augmenting path를 찾은 것이니 매칭 개수를 늘려준다.

그렇지 않다면, $A'$에 있는 정점들은 $v$를 제외하고는 전부 $B'$의 매칭 반대편에 있는 정점들이다. 고로 $|A'| = |B'| + 1$을 만족한다. 가정에 의해서 $A'$ 에서 $B \setminus B'$ 로 가는 간선이 존재한다. 그러한 에지를 $e = \{a, b\}$ 라 하면, $v$에서 $a$로 가는 alternating path가 존재하니 $b$로 가는 alternating path 역시 존재할 것이다. 하지만 $b \in B \setminus B'$이기 때문에, 가정에 모순이다. 

고로 매칭을 찾지 못한 정점 $v \in A$에서 항상 augmenting path를 찾을 수 있고, 이렇게 매칭되지 않은 정점을 하나 하나 지워가면 된다.

증명 2. 수학적 귀납법을 사용한다. $|A| = 1$이면, $|N(A)| \geq 1$이니 자명하다. $|A| \geq 2$를 가정하자.

$A$의 공집합이 아니며($X \neq \emptyset$) 전체집합도 아닌($X \neq A$) 모든 부분집합 $X \subset A$에 대해 $|N(X)| \geq |X| + 1$를 만족한다고 하자. $G$에서 임의의 간선 $e = \{u, v\}$를 제거했을 때, 모든 부분집합 $Y \subset A\setminus\{u\}$에 대해서, $|N(Y)| \geq |Y|$ 가 성립한다. $Y$가 공집합이면 자명하고, $e$를 제거하기 전의 $G$에서 $N(Y)$가 이웃한 정점의 집합이라고 하면, 거기서 많아야 한 개의 원소($v$)만 빠지기 때문이다. 고로, 귀납 가정에 의해서 $A\setminus\{u\}$의 모든 원소를 매칭시키고, 거기에 $e$를 추가하면 된다.

그렇지 않다면, $|N(X)| = |X|$ 인 $A$의 부분집합 $X$가 존재한다. 이 때 $1 \geq |X| < |A|$이다. 귀납 가정에 의해 $X$의 모든 정점을 매칭시킬 수 있다. 한편, $A\setminus X$와 $N(A)\setminus N(X)$ 로 이루어진 이분 그래프도 결혼 조건을 만족한다. 귀류법으로 그렇지 않은 부분집합 $Y \subset (A\setminus X)$ 가 존재한다 하자. $|N(Y)| < |Y|$ 인데, $N(Y)$와 $N(X)$는 서로소고, $X$와 $Y$도 서로소니, 둘을 합쳐주면 원래 그래프에서 $|N(X\cup Y)| < |X\cup Y|$ 인 부분 집합을 찾게 되기 때문이다. 고로, 귀납 가정에 의해서 $A\setminus X$와 $N(A)\setminus N(X)$ 간의 매칭을 찾을 수 있고, 두 개의 매칭 집합을 합쳐주면 된다.

증명 3. 가정에 의해 $A$의 모든 정점의 degree는 1 이상이다. 결혼 조건을 만족하며, $A$의 모든 정점의 degree를 1 이상으로 만들고, 간선의 개수가 최소인 $G$의 서브그래프를 $H$라 하자. 이 때, $H$에서 $A$의 모든 정점의 degree는 1이다. 만약 이를 만족한다면, 결혼 조건에 의해 $B$의 어떤 정점도 degree가 2가 될 수 없기 때문에 $H$는 $A$의 완벽 매칭이 된다. 이는 귀류법을 통해 보일 수 있다. $deg_{H}(v) > 1$인 $v \in A$가 존재한다 하고, 이 정점과 연결된 간선 중 임의로 두개를 골라 $e_1 = \{a, b_1\}, e_2 = \{a, b_2\}$라 하자. 

$H$가 조건을 만족하는 최소 간선의 서브그래프이기 때문에, $H$에서 $e_1, e_2$ 간선을 제거한 subgraph인 $H - e_1$, $H - e_2$는 결혼 조건을 만족하지 않는다. 고로, $H - e_1$에서, $|N(A_1)| < |A_1|$인 $A_1 \subset A$, $H - e_2$에서, $|N(A_2)| < |A_2|$인 $A_2 \subset A$가 존재한다. 또한, $a \in A_1 \cap A_2$를 만족한다 (그렇지 않다면 $H$가 결혼 조건을 만족하지 않으니까). 이 때, $A_1 \cap A_2 \setminus \{a\}$가 $G$에서 결혼 조건을 만족하지 않음을 보인다. 편의상 $B_i = N(A_i)$ 라 하자. 

$N(A_1 \cap A_2 \setminus \{a\})| \leq |B_1 \cap B_2| = |B_1| + |B_2| - |B_1 \cup B_2|$

이 때, $B_1 \cup B_2$는 $b_1, b_2$를 모두 포함하고 있다. $a \in A_1 \cap A_2$ 이기 때문에 $b_1 \in A_2$, $b_2 \in A_1$을 만족하기 때문이다. 고로

$|B_1| + |B_2| - |B_1 \cup B_2| = |B_1| + |B_2| - |B_1 \cup B_2| = |B_1| + |B_2| - |N_{H}(A_1 \cup A_2)|$

$|B_1| + |B_2| - |N_{H}(A_1 \cup A_2)| \leq |A_1| - 1 + |A_2| - 1 - |N_{H}(A_1 \cup A_2)|$

$|A_1| - 1 + |A_2| - 1 - |N_{H}(A_1 \cup A_2)| \leq |A_1| - 1 + |A_2| - 1 - |A_1 \cup A_2|$

$|A_1| - 1 + |A_2| - 1 - |A_1 \cup A_2| = |A_1 \cap A_2| - 2 = |A_1 \cap A_2 \setminus \{a\}| - 1$

$N(A_1 \cap A_2 \setminus \{a\})| \leq |A_1 \cap A_2 \setminus \{a\}| - 1$

고로 $H$라는 $A$의 완벽 매칭이 존재한다. 

문제 17

결혼 정리를 그대로 사용하면 된다. $k \geq 1$이라 하자. 임의의 남자의 부분집합 $X$에 대해서, 이들의 뽀뽀 횟수의 총 합은 $k|X|$이다. 고로 이들과 뽀뽀한 여자 $N(X)$의 뽀뽀 흿수의 총합은 최소 $k|X|$ 번 이상이다. $k|N(X)| \geq k|X|$ 이고, 양변을 $k$로 나누면 $|N(X)| \geq |X|$가 된다. 홀의 결혼 정리에 의해서 $n$쌍을 만들 수 있다.

참고로 Q4의 답은 틀렸다이다. 남자 3명, 여자 3명일 때, 남1 - 남2, 남1 - 여1, 남2 - 여1, 여2 - 여3, 여2 - 남3, 여3 - 남3 이 뽀뽀했다고 하면, 모든 사람의 횟수가 2번이지만, 많아야 2쌍밖에 만들지 못한다.

문제 18    풀이 틀림

먼저 행렬의 음수 원소들을 모두 제거해주자. $M_{i, j} < 0$인 원소가 존재한다면, $A_{i, j} = 1$을 만족하는 행렬 $A \in P$가 존재한다. 이 행렬의 $M{i, j}$ 배를 $M$에 더해주면, 음수 원소가 최소 1개 사라지며, 합 역시 일정하게 유지된다. 이 방법으로 $M$의 모든 원소가 0 이상이게 할 수 있다.

$M$의 모든 원소가 0 이상이며 행과 열의 합이 일정할 경우, $M$을 $P$의 선형 결합으로 표현할 수 있음을 보인다. $f(M)$을 $M$의 임의의 행의 수의 합이라 하면, $f(M)$에 대해서 귀납법을 사용한다. 기저 조건은 $f(M) = 0$으로, 자명하다. 

$f(M) \geq 1$일 때, 어떠한 행렬 $X \in P$가 존재해서, $M - X$의 모든 원소가 0 이상이게 할 수 있음을 보인다. 행과 열의 합이 여전히 일정하게 유지되고, $f(M - X) + 1 = f(M)$ 인 고로 귀납 가정에 의해서 $M - X$를 선형 결합으로 표현할 수 있기 때문이다. 이 때, $|A|, |B| = n$인 이분 그래프 $G$를 만들고, $M_{i, j} > 0$일 때 $A_i$와 $B_j$의 간선을 이어준다면, 이 그래프의 완벽 매칭이 $X$에 대응됨을 알 수 있다. 매칭된 쌍 $(A_i, B_j)$를 $X_{i, j} = 1$로 표현하면 $X \in P$이고, $M_{i, j} - X_{i, j} \geq 0$이 보장되기 때문이다. 고로 이러한 완벽 매칭이 존재함을 보이면 된다.

이는 홀의 결혼 정리로 증명 가능하다. 모든 $S \subset A$에 대해, $k|S|= \sum_{i \in S, j \in B}{a_{i, j}} =  \sum_{i \in S, j \in N(S)}{a_{i, j}} \leq  \sum_{i \in A, j \in N(S)}{a_{i, j}} = k|N(S)|$ 이고, 고로 $k|S| \leq k|N(S)|$ 이다. 귀납 가정에 의해서 $k > 0$이었으니 $|S| \leq |N(S)|$이고 결혼 조건을 만족하니 $X$를 찾을 수 있다.

문제 19

색을 $1, 2\cdots k+1$ 까지의 양의 정수로 표현하자. 모든 정점의 차수가 $k$ 이하일 때 $k+1$ 이하의 정수만으로 색칠이 가능함을, $|V(G)|$에 대한 귀납법으로 보인다. 

$|V(G)| = 1$인 경우에는 해당 정점에 1번 색을 칠해주면 된다. $|V(G)| \geq 2$라면, 임의의 정점 $v \in V(G)$를 제거한 그래프를 생각하자. 정점의 개수가 하나 줄어드니, 귀납 가정에 의해서 색칠을 구할 수 있다. 이제 에지를 추가하고 $v$에 색을 부여해야 하는데, $v$와 인접한 정점의 개수가 많아야 $k$개이니, $v$에 적을 경우 모순이 생기는 수들도 많아야 $k$개임을 알 수 있다. 고로, 모순 없이 $v$에 적을 수 있는 수가 최소 하나 존재한다. 이 수를 적으면 된다.

문제 20

두가지 증명 방법을 http://koosaga.com/209 에 적어놓았다.

문제 21

문제 22

추가 문제

PS를 할 때 도움이 될 만한 알고리즘적인 문제들로 구성했다. 모든 문제들의 증명 방법은, 수학적 귀납법을 사용해서 답을 찾는 알고리즘이 항상 존재함을 보이는 방식이며, 또한 여기 적힌 대부분의 알고리즘이 실제로 구현 가능하다. 

참고로, 7-1번은 수학적 귀납법과 상관 없는 자료 구조 문제이다.

추가 문제 1. (IMO 2013 P1) 임의의 두 양의 정수 $k, n$에 대하여, 다음의 성질을 만족하는 (서로 다를 필요는 없는) $k$ 개의 양의 정수 $m_1, m_2, \cdots, m_k$가 존재함을 증명하고, 이 정수들을 찾는 다항 시간 알고리즘을 제시하라.

 $1 + \frac{2^k - 1}{n} = (1 + \frac{1}{m_1})(1 + \frac{1}{m_2})\cdots(1 + \frac{1}{m_k})$

추가 문제 2. (NEERC 2007 A, 코드포스 링크) 평면 위에 $n$개의 빨간 점과 파란 점이 있다. 어느 세 점도 한 직선 상에 없을 때. 빨간 점과 파란 점 간의 교차하지 않는 매칭이 존재함을 증명하고, 이 매칭을 찾는 $O(n^2lgn)$ 알고리즘을 제시하라. 

추가 문제 3. (KOI 2016 중등부 4번, BOJ 13307) 평면 위에 $2n$개의 빨간 점과 $n$개의 파란 점이 있다. 어느 세 점도 한 직선 상에 없을 때, 빨간 점 - 파란 점 - 빨간 점을 잇는 교차하지 않는 $n$개의 길이 2 단순 경로가 존재함을 증명하고, 이 경로를 찾는 $O(n^2lgn)$ 알고리즘을 제시하라. 

추가 문제 4. (IMO 2017 P5, 코드포스 링크) 정수 $N \geq 2$이 주어져 있다. $N(N+1)$명의 축구선수들이 한 줄로 서있고, 이들 중 어느 두 사람도 키가 서로 같지 않다. 민규는 이 선수들 중 $N(N-1)$명을 빼내, $2N$명의 선수들을 남기되, 남아 있는 선수들이 다음과 같은 $N$개의 조건을 만족하도록 한다.

(1) 가장 키가 큰 두 선수 사이에는 아무도 없다.

(2) 세번째로 키가 큰 선수와 네번째로 키가 큰 선수 사이에는 아무도 없다.

⋮

($N$) 가장 키가 작은 두 선수 사이에는 아무도 없다.

이렇게 하는 것이 항상 가능함을 보이고, 그 방법을 찾는 다항 시간 알고리즘을 제시하라. 

추가 문제 5. (IOI 2006 Joining Points) 위쪽 모서리가 두 개의 빨간 점, 아래쪽 모서리가 두 개의 파란 점으로 이루어진 정사각형이 있으며, 정사각형 안에 빨간 점과 파란 점이 존재한다. 어떤 세 점도 한 직선에 존재하지 않는다. 평면 상에서 빨간 점들을 선분으로 연결시킨 스패닝 트리와, 파란 점을 선분으로 연결 시킨 스패닝 트리를 생각해 보자. 임의의 선분 쌍이 끝점을 제외하고 만나지 않는 스패닝 트리가 존재함을 증명하고, 이를 다항 시간에 찾는 알고리즘을 제시하라.

추가 문제 6. (Japan IOI 2012 Selection 변형). 평면 상에 $n$개의 빨간 점과 파란 점이 최소 1개 이상 존재한다. 어떤 세 점도 한 직선 안에 존재하지 않을 때, 이들이 겹치지 않는 스패닝 트리를 가질 필요 충분 조건이 무엇인지 보이고, 조건을 만족할 때 그러한 스패닝 트리를 찾는 다항 시간 알고리즘을 제시하라.

추가 문제 7. (IMO 2009 P6) 주어진 서로 다른 양의 정수 $a_1, a_2, \cdots, a_n$에 대하여 $s = a_1 + a_2 + \cdots + a_n$을 제외한 임의의 $n-1$개의 서로 다른 양의 정수들로 이루어진 집합 $M$이 있다. 메뚜기 한 마리가 수직선 위의 원점 0에서 시작하여 매번 양의 방향으로 총 $n$번의 점프를 하는데, 점프 거리를 순서대로 나열한 것이 $a_1, a_2, \cdots, a_n$의 재배열이 되도록 점프한다. 이 메뚜기가 $M$의 원소를 좌표로 갖는 수직선 상의 점들을 하나도 밟지 않고 $n$번의 점프를 할 수 있는 $a_1, a_2, \cdots, a_n$의 재배열이 존재함을 보이고, 이 재배열을 구하는 $O((n+m)^2)$ 알고리즘을 제시하라.

추가 문제 7-1. (KAIST 2017 봄 프로그래밍 대회, BOJ 14558) 추가 문제 7의 알고리즘을 $O((n+m)lg^2(n+m))$ 으로 최적화하라.