간호-자연 2번

(가) [외판원 문제] 어느 외판원이 $\displaystyle n$개의 도시를 방문하여 제품을 판매하려고 한다. 모든 도시를 한 번씩만 방문하려고 할 때, 어느 순서로 도시를 방문해야 여행 거리가 최소가 되는가? 이러한 물음을 일반적으로 “외판원 문제”라고 한다. 여행 거리가 최소인 경로를 찾는 한 방법으로 다음을 생각해 볼 수 있다. $\displaystyle n$개의 도시를 방문하는 여행 경로는 $\displaystyle n!$개가 있다. 각각의 여행 경로에 대해 여행 거리를 계산하면 여행 거리가 최소인 경로를 찾을 수 있다. 비록 이론적으로는 도시의 수에 상관없이 이 방법을 적용할 수 있지만, 실질적으로는 작은 $\displaystyle n$에 대해서만 이 방법을 적용할 수 있다. 그 이유는 $\displaystyle n$이 아주 크지 않은 경우라도 계승 $\displaystyle n!$은 현실적으로 다룰 수 없을 정도로 매우 크기 때문이다. 예를 들어, 방문해야 할 도시의 수가 $\displaystyle 50$이라면 모든 경로의 수는$\displaystyle 50!=30414093201713378043612608166064768844377641568960512000000000000>10^{64}$이다. 이 경우, 각 여행 거리를 아주 빠른 컴퓨터를 사용하여 계산한다고 해도 엄청난 시간이 걸린다. 한 예로, $\displaystyle 1$초에 $\displaystyle 100$조$\displaystyle \left(=10^{14}\right)$개의 여행 거리를 계산할 수 있는 컴퓨터 $\displaystyle 1$억$\displaystyle \left(=10^{8}\right)$대를 사용하면, 답을 구하는 데 적어도 $\displaystyle 10^{42}$초가 필요하다. 참고로 우주의 나이는 약 $\displaystyle 4\times 10^{17}$초라고 알려져 있다. 계승은 이처럼 빨리 커지는 수인데, 이 성질을 계승은 지수함수보다 훨씬 빨리 커진다는 표현으로 나타낸다. 이 표현의 타당성은 임의의 실수 $\displaystyle t$에 대해, $\displaystyle n!$과 $\displaystyle t^{n}$의 비가 $\displaystyle n$이 커질 때 어떻게 되는지를 보고 판단할 수 있다. 계승의 이런 성질로 인해서 외판원 문제는 어려운 문제로 알려져 있다.

(나) [자연로그의 밑 $\displaystyle e$] 일반항이 $\displaystyle a_{n}=\left(1+\frac{1}{n}\right)^{n}$인 수열 $\displaystyle \{a_{n}\}$은 증가수열이다. 즉, 모든 자연수 $\displaystyle n$에 대하여 $\displaystyle a_{n}<a_{n+1}$을 만족한다. 그리고 $\displaystyle n$이 무한히 커지면 수열 $\displaystyle \{a_{n}\}$은 자연로그의 밑 $\displaystyle e$에 한없이 가까워진다. 즉, $\displaystyle \lim_{n\to\infty}a_{n}=e=2.718\cdots$이다.

(다) [수학적 귀납법] 자연수 $\displaystyle n$에 대한 명제 $\displaystyle p(n)$이 모든 자연수 $\displaystyle n$에 대하여 성립함을 증명하려면 다음의 두 가지를 보이면 된다.① $\displaystyle n=1$일 때 명제 $\displaystyle p(n)$이 성립한다.② $\displaystyle n=k$일 때 명제 $\displaystyle p(n)$이 성립한다고 가정하면 $\displaystyle n=k+1$일 때도 명제 $\displaystyle p(n)$이 성립한다.

(라) [조임 정리] 세 수열 $\displaystyle \{x_{n}\}$, $\displaystyle \{y_{n}\}$, $\displaystyle \{z_{n}\}$이 모든 자연수 $\displaystyle n$에 대해 $\displaystyle x_{n}<y_{n}<z_{n}$을 만족한다고 하자. 만약 수열 $\displaystyle \{x_{n}\}$과 $\displaystyle \{z_{n}\}$이 수렴하고 그 극한값이 $\displaystyle C$로 같다면, 즉, $\displaystyle \lim_{n\to\infty}x_{n}=\lim_{n\to\infty}z_{n}=C$라면, 수열 $\displaystyle \{y_{n}\}$은 수렴하고 $\displaystyle \lim_{n\to\infty}y_{n}=C$이다.

(마) [극한의 성질] 수열 $\displaystyle \{b_{n}\}$이 $\displaystyle \lim_{n\to\infty}b_{n}=0$을 만족하면, $\displaystyle \lim_{n\to\infty}\left(b_{n}\right)^{n}=0$이다.