Q3. 수학적 귀납법을 이용한 증명

양의 정수 (n)에 대하여

[ 1+2+3+\cdots+n=\frac{n(n+1)}{2} ]

임을 증명하자.

1. 기초 단계

(n=1)일 때,

[ 1=\frac{1(1+1)}{2}=1 ]

이므로 명제가 성립한다.

2. 귀납 가정

어떤 양의 정수 (k)에 대하여 다음이 성립한다고 가정하자.

[ 1+2+3+\cdots+k=\frac{k(k+1)}{2} ]

3. 귀납 단계

그러면

[ \begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}{2}+(k+1)\ &=\frac{k(k+1)+2(k+1)}{2}\ &=\frac{(k+1)(k+2)}{2}. \end{aligned} ]

따라서

[ 1+2+\cdots+k+(k+1) =\frac{(k+1)((k+1)+1)}{2} ]

이다.

기초 단계와 귀납 단계가 모두 성립하므로, 수학적 귀납법에 의하여 모든 양의 정수 (n)에 대해

[ \boxed{1+2+3+\cdots+n=\frac{n(n+1)}{2}} ]

가 성립한다.

Q4. 비둘기집 원리의 적용

사람들을 비둘기라고 하고, 태어난 달을 비둘기집이라고 생각하자.

• 비둘기: 30명
• 비둘기집: 12개월

각 달에 태어난 사람이 최대 2명이라고 가정하면, 전체 인원은 최대

[ 12\times 2=24 ]

명이 된다.

그러나 실제 사람 수는 30명이므로 이는 모순이다. 따라서 적어도 한 달에는 3명 이상의 사람이 태어나야 한다.

또는 비둘기집 원리에 따라 어떤 달에 태어난 사람 수는 적어도

[ \left\lceil \frac{30}{12}\right\rceil

\left\lceil 2.5\right\rceil =3 ]

명이다.

따라서

[ \boxed{\text{적어도 세 명의 사람은 같은 달에 태어났다.}} ]

Q5. 그래프 (G)의 평면성

주어진 그래프는

[ V(G)={A,B,C,D,E} ]

이고,

[ E(G)={AB,BC,CD,DE,EA,AC} ]

이다.

먼저 다음과 같이 오각형을 그린다.

[ A\text{--}B\text{--}C\text{--}D\text{--}E\text{--}A ]

그리고 오각형 내부에 대각선 (AC)를 추가한다.

개념적인 그림은 다음과 같다.

        A
      /   \
     E     B
      \   /
       D-C
          \ 

보다 정확하게는 (A,B,C,D,E)를 오각형의 꼭짓점에 배치하고, 오각형의 변

[ AB,\ BC,\ CD,\ DE,\ EA ]

을 그린 뒤, 오각형 내부에 선분 (AC)를 그리면 된다. 이때 모든 변은 서로 교차하지 않는다.

따라서 그래프 (G)는 평면 그래프이다.

[ \boxed{G\text{는 평면 그래프이다.}} ]

또한 이 그래프에는 (K_5) 또는 (K_{3,3})의 세분(subdivision)이 포함되어 있지 않으므로, 쿠라토프스키 정리와도 모순되지 않는다.