i. n이 짝수일 때
우선, 사각형은 겹치지 않게 대각선을 그리려면 한 개 밖에 못 그리고, 그러면 모든 점이 짝수 개의 대각선이 지나도록 대각선을 그리는 것이 불가능.
n=2k로 두자. (k>2)
1. 1번 점과 3번 점을 잇는 대각선을 그리고, 3번 점과 5번 점을 잇는 대각선을 그리고, ... 2k-1번과 1번 점을 잇는 대각선을 그린다.
2. 그러면 겉에 k개의 삼각형과 안쪽에 볼록다각형인 k각형이 나온다.
k가 짝수이면 1번 과정을 반복한다.
k가 3이면 자명.( n=6일 때 성립)
k가 5 이상의 홀수이면 멈춘다. 이후 과정은 경우 ii에서 후술.
ii. n이 홀수일 때
n=2k-1로 두자.(문제 조건상 k>=3)
대각선을 다음과 같이 그리자.
1. 1번 점이랑 3번 점을 잇는 대각선을 그리고, 3번 점이랑 5번 점을 잇는 대각선을 그리고 ... 2k-3번 점이랑 2k-1번 점을 잇는 대각선을 그린다.
2. 그러면 겉에 k-1개의 삼각형과 안쪽에 대각선들과 정n각형의 한변으로 이루어진 k각형이 존재한다. 그런데 1번 점과 2k-1번 점은 현재 지나는 대각선이 1개이므로 추가로 지나는 대각선을 그려야 한다.
k=3일 때는 1번 과정을 거치면 더 이상 겹치지 않게 대각선을 그리지 못하고, 그러면 1번 점과 5번 점을 지나는 대각선의 개수가 1개이므로 조건 성립 불가. (n=5일 때 성립 불가)
k=4이면 1번 점과 7번 점을 지나는 대각선이 1개여서 추가로 대각선을 그려야 하는데, 안쪽 도형이 사각형이어서 겹치지 않게 대각선을 그리려면 1개 밖에 못 그리고, 그러면 1번 점과 7번 점을 지나는 대각선의 개수가 동시에 짝수 개가 안되므로 조건 성립 불가. (n=7일 때 성립 불가)
k>=5이면 1번 점과 2k-1번 점을 지나면서 동시에 특정한 점을 동시에 지나는 두 대각선을 그리는게 가능. 그 특정한 점을 m번 점(단, m은 5이상 2k-5이하의 홀 수)이라 하면 안쪽의 k각형은 1번 점, m번 점, 2k-1번 점을 꼭짓점으로 하는 삼각형과 (m+1)/2각형, (k+1)-(m+1)/2각형이 나온다. 두 도형은 전부 원래 도형의 대각선으로 이루어진 도형이고, 현재 그림은 각 꼭짓점을 지나는 대각선의 개수가 모두 짝수 개이다. 그리고 정n각형이나 볼록다각형인 n다각형을 똑같은 번호를 가진 점을 지나도록 대각선을 그리면 똑같은 양상으로 분할되므로 문제가 없다.
그러면 현재 정n각형은 총 k개의 삼각형과 (m+1)/2각형(이하 A각형), (k+1)-(m+1)/2각형(이하 B각형)으로 분할된다. 그리고 각 도형들은 모두 볼록다각형.
3. A나 B중 하나라도 짝수가 있다면 경우 i의 1번 과정을 반복해서 홀수로 만들면 된다. 그러므로 A와 B가 홀수인 경우만 고려.
그러면 위의 1번 과정과 2번 과정을 각각 반복할 수 없을 때까지 반복하면 최종적으로는 n각형이 삼각형, 사각형, 오각형, 육각형, 칠각형, 팔각형으로 분할 된다. 팔각형은 i번 경우를 한 번 반복하면 사각형이 나오므로 분할 불가, 오각형, 사각형, 칠각형은 앞에서 분할 불가라고 했으므로, n각형이 최종적으로 삼각형들로 분할 되려면 위 과정을 반복했을 때 마지막 홀수 다각형이 삼각형과 육각형으로만 분할되어야 한다. 즉, 최종적으로 n각형이 삼각형들로 분할되는 것은 마지막의 홀수 다각형을 분할 시 A=B=3×2^a(a는 0이상의 정수)이 나오는 경우나 마찬가지이고 그러면 이전 도형은 n=2k-1=2(A+B)-3, 즉 3의 배수가 됨. 즉 n이 3의 배수이면 분할된 도형들도 모두 변의 개수가 3의 배수가 되는 도형들로 만들 수 있고, 이는 최종적으로 삼각형들로 분할 된다.
i의 경우와 ii의 경우 모두 고려시, n이 3의 배수이면 문제 조건에 맞는 분할이 성립한다.
