삼각형 123을 삼각분할하자. 변 12위의 점에는 1 또는 2를 붙이고, 변 13위에는 1 또는 3을 붙이고, 변 23위에는 2 또는 3을 붙이자. 또, 삼각형 내부의 점에는 1, 2, 3 중 하나를 붙이자. 이 때, 삼각분할 된 삼각형 중 세 꼭짓점에 1, 2, 3이 하나씩 나타나는 삼각형을 완전삼각형이라고 하자. 완전삼각형의 개수가 홀수임을 보여라.
좋아요
0
글쎄요
0
어려워요
0
-
뭔가 문제들이 제가 영재고 대비 공부하는 교재에 나온 문제들이랑 많이 일치하네요. (이 문제는 sperner 보조정리이네요)
-
슈페르너 정리 관련 문제군요.
일단 간단하게 1차원으로 생각해봅시다.
1-2-1-1-2-1-2 와 같이 양 끝에 1, 2가 있는 상황을 형성했습니다. 여기서 1-2, 2-1의 개수는 항상 홀수 개일까요?
네 그렇습니다. 크게 3가지 방법이 있는데요, 더블카운팅, 변화량, 시각화가 있습니다.
이 중 더블카운팅이 가장 효과적인 방법입니다.
1-2의 개수를 x, 1-1의 개수를 y라고 합시다.
여기서 카운팅되는 1의 횟수를 세면 x+2y = 2(내부의 1개수) + (외부 1 개수)입니다.
내부에 위치하는 1은 2번, 외부의 1은 1번 세지는 것이죠. 외부에 1이 1개이므로 mod2 에 대해 x는 1입니다.
이를 사용합니다.
n차원에서 (1,2,...n)의 개수 또한 sperner labeling(위 방법을 부르는 말입니다)을 시행했을 때 홀수개입니다.
아까 전처럼 (1,2,...,n-1)이 세어지는 횟수로 더블카운팅을 진행합니다.
(1,2,...,n)이 x개, (1,1,2,3,...,n-1) (1,2,2,3,...,n-1), .... (1,2,3,...,n-1,n-1)이 y개라 합시다.
x+2y = 2(내부 (1.2....n-1)의 개수) + (외부 (1,2,...n-1) 개수)입니다.
여기서 외부 개수가 바로 귀납적 성질이라는 것입니다! 따라서 x는 항상 홀수죠.
