문제는 https://arca.live/b/math/63656531
ㅇㅇ님 풀이는 여기: https://arca.live/b/math/63686648
-----------------------------------------------------------------------------------------
정n각형이 있다.(n>=4)
이 도형을 이 정n각형의 대각선들로 쪼갤 건데, 단, 다음의 조건을 모두 만족해야 한다.
i) 모든 대각선은 겹치지 않는다(정n각형의 꼭짓점에서 만나는 것은 겹치는게 아니다)
ii) 모든 꼭짓점에 대해 지나는 대각선의 개수는 짝수개이다, 단 0도 짝수로 생각한다.
iii) 정n각형이 쪼개진 최종 모양은 모두 삼각형이어야 한다.
이때 위와 같은 분할이 가능한 n의 형태를 모두 구하시오.
-----------------------------------------------------------------------------------------
문제의 분할이 가능한 모든 자연수의 집합을 T 라 하자. 문제에서는 n ≧ 4 로 한정했지만 3 ∈ T 로 놓는다.
또한 문제의 분할은 정다각형이 아닌 볼록다각형에서 일반적으로 성립한다.
이제 n > 3, n ∈ T 인 볼록다각형인 n각형의 분할을 생각하자.
(편의상 그림에서 오목다각형인 것처럼 그려져 있지만 볼록다각형이다. 양해 바람.
)
n 이 3이 아니므로 양수 개수의 대각선이 지나는 점이 존재한다. 이 중 하나의 점을 A 라 하자.
A 를 지나는 대각선 중 시계방향으로 첫 번째 대각선을 AB, 두 번째 대각선을 AC 라 하자.
그림처럼 정n각형의 바깥 선을 따라서 A와 B 사이에 A1, A2, ..., Ak 의 점들이 있다고 할 때 (A1, ..., Ak는 C를 포함하지 않는 쪽)
AB는 A를 지나는 대각선 중 시계방향으로 첫 번째 대각선이므로 A와 A1, ..., Ak 사이에는 대각선이 없다.
또한 A1, ..., Ak 는 각각 짝수개의 대각선이 지난다.
그런데 볼록다각형 A A1 A2 ... Ak B 의 각 꼭지점을 지나는 대각선의 개수의 합은 짝수이므로 (∵ 개개의 대각선이 2번씩 세어지므로)
볼록다각형 A A1 A2 ... Ak B 내부에서 B를 지나는 대각선의 개수 역시 짝수개이다.
즉 볼록다각형 A A1 A2 ... Ak B 역시 문제의 분할을 만족하는 도형이다.
따라서 이 볼록다각형의 꼭지점의 수를 n1 이라고 하면, n1 ∈ T
쪼개진 최종 형태는 모두 삼각형이어야 하므로 BC는 대각선 혹은 원래의 n각형의 변으로 연결되어야 한다.
그런데 B를 지나며 A A1 A2 ... Ak B 내부에 있는 대각선의 숫자는 짝수이므로
만약 BC 가 원래의 n각형에서 변으로 연결되어 있다면, B를 지나는 대각선의 숫자는 AB 까지 합쳐서 홀수가 되어 모순이다.
따라서 BC를 지나는 선은 원래의 n각형의 대각선이다.
정n각형의 바깥 선을 따라서 B와 C 사이에 B1, B2, ..., Bt 의 점들이 있다고 할 때 (B1, ..., Bt는 A를 포함하지 않는 쪽)
B를 지나며 B1, ..., Bt 를 연결하지 않는 대각선의 숫자는 짝수이다.
따라서 B를 지나며 B1, ..., Bt 를 연결하는 대각선의 숫자 역시 짝수이다.
그러면 볼록다각형 B B1 ... Bt C 의 각 꼭지점을 지나는 대각선의 개수의 합은 짝수이므로
볼록다각형 B B1 ... Bt C 내부에서 C를 지나는 대각선의 개수 역시 짝수개이다.
즉 볼록다각형 B B1 ... Bt C 역시 문제의 분할을 만족하는 도형이다.
따라서 이 볼록다각형의 꼭지점의 수를 n2 이라고 하면, n2 ∈ T
AC 로 쪼갠 도형 쪽도 마찬가지로 문제의 분할을 만족하는 도형이 되므로 (똑같은 말이 되풀이되므로 생략)
AB, BC, CA 로 나누어진 도형의 꼭지점 숫자를 각각 n1, n2, n3 라 하면, 다음이 성립한다.
n1, n2, n3 ∈ T
n = n1 + n2 + n3 - 3
이제 3의 배수가 아닌 어떤 m 이 m ∈ T 를 만족한다고 가정하자.
m > 3 인 경우 m = m1 + m2 + m3 - 3 , m1, m2, m3 ∈ T 를 만족하는 m1, m2, m3 가 존재해야 하는데
만약 m1, m2, m3 가 모두 3의 배수라면 m 또한 3의 배수여야 하므로, m1, m2, m3 중 3의 배수가 아닌 것이 존재한다.
또 m1, m2, m3 < m 이므로
3의 배수가 아닌 m에 대해 m ∈ T 인 경우 항상 m' < m, m' ∈ T 이며 3의 배수가 아닌 m' 이 존재한다.
이 과정을 반복하면 v ∈ T, v < 3 인 v 를 얻을 수 있다.
이는 모순이므로 n ∈ T 인 모든 n 에 대해서 n 은 3의 배수이다.
이제 3의 배수인 모든 자연수 n에 대해서 n ∈ T 이 성립함을 보이자.
n = 3, 6 에 대해서는 자명하게 성립한다.
또한 n = 3k 인 경우에 성립할 때
대각선이 지나지 않는 꼭지점과 그 양쪽의 꼭지점을 잇는 대각선으로 이루어진 삼각형을
그림과 같이 육각형으로 교체하면 n = 3k + 3 인 경우의 분할을 만들 수 있다.
따라서 3의 배수인 모든 자연수에 대해 문제의 분할이 성립한다.
