티스토리 뷰

공부/Math

수학적 귀납법

구사과 2017. 9. 30. 11:51

(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 성질 -> 강한 수학적 귀납법

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

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

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


PDF 연습 문제 (16/22)

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

문제 1

문제 2

문제 3

문제 4

문제 5

문제 6

문제 7

문제 8

문제 9

문제 10

문제 11

문제 12

문제 13

문제 14

문제 15 / 문제 16

문제 17

문제 18    풀이 틀림

문제 19

문제 20

문제 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))$ 으로 최적화하라. 

댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday