슬기로운 수학생활 28번
만나지 않는 두 선분
문제 출제자 : 백진언 미시간 대학교 수학과 박사과정생
평면에 
개의 점들이 있어서 어떤 세 점도 한 직선위에 없다. 이 점들의 집합을 
라 하자. 양 끝점이 에 있는 서로 다른 
개의 선분들이 있다. 그러면 그 선분들 중에 두개의 서로 만나지 않는 선분이 있음을 보이자. 이때 서로 만나지 않는다는 것은 양 끝점을 포함해서 교차하는 점이 없다는 것이다.
백진언 연구원의 팁
힌트를 주면 핵심적인 부분이 전부 공개될 것 같다! 의외로 쉽지 않은 문제이지만 작은 예시들부터 시도해보면서 증명할 수 있는 성질들을 조금씩 찾아보자.
-
문제에 어느 세 점도 한 점 위에 있지 않은 건,n>=3이고,
제가 잘못 이해한 거면 그럴 수 있지만,n=3일 때도 성립하는지가 확실하지 않네요.(제가 문제를 이해한 대로 하면요.)
제가 이해한 것 중 잘못된 게 있나요?
n개의 점이 집합 X에 속하고,어쨌든 양 끝점이 X에 속해 있는 선분 n+1개 중 서로 만나지 않는 선분이 있음을 보이라는 것인가요?
-
다시 도전
-
다시 도전
-
'~~로 생각'이라는 애매한 표현보다 더 정확한 표현을 써주셨으면 좋겠습니다 (귀류법 가정을 적용한다거나, 무엇을 어떻게 생각한다는 건지가 말로 써져 있게요)
P가 선분들의 집합인가요, 아니면 선분들 안에 있는 점들의 집합인가요? P랑 A의 교집합은 만약 P가 선분들의 집합이면 원칙적으로는 공집합입니다. P의 원소들은 선분인데 A의 원소들은 점이니까 둘이 다르지요. 만약 P가 선분들 안에 있는 점들의 집합이라면, P와 A의 교집합에는 경우 (한 선분이 한 점은 A에 있고 다른 점은 X'에 있음) 와 (한 선분이 두 점 모두 A에 있음) 을 구분해야 할 거 같습니다.
좋아요1 -
아하 수정해서 올리겠습니다!
좋아요0
-
-
그러면 n=7일 때, 이런 모양도 성립하나요? 실제 n=7일 때 사각형과 삼각형으로 따로 연결해 선분 8개를 그어 점들이 모두 서로 연결되지는 않는데,어쨌든 이러면 최소 만나지 않는 선분이 생깁니다. 이런 경우도 가능하다 하는 것이죠?
-
-
-
n개의 점을 찍어 그 모양이 볼록 다각형이면 저는 어느 정도 증명할 수 있는데,다른 모양까지 고려하니 간단하진 않네요..
볼록 다각형이 되면 일단 선분을 그어 n개의 선분을 완성 시킨 뒤,대각선을 하나 긋는 방식이 되는데,이때 대각선 이외로 한 선분당 만나지 않는 선분이 1개 이상으로 여러 쌍인 건 아는데,이건 그 점을 정확히 볼록다각형으로 연결시키는 경우만 성립해서...(심지어 그 점을 잘 연결시킬 때,볼록다각형으로 나오지 않아도 방법이 있는데,그걸 증명하는 것은 간단하지가 않네요.)
-
저는 지금까지 (형태가 다각형이라는 거지, 선분이 서로 만날 수도 있음. 다각형을 꼬아 놓은 형태도 될 수 있음. )다각형 형태로 n개의 선분을 연결할 때, 거기에 선분 한 개만 추가해도 만나지 않는 선분이 생긴다는 것을 증명하면 전부 증명된다는 것을 알아냈어요.
그리고 최대한 선분을 전부 만나게 하려고 해 보니, 특정한 형태에서만 만나지 않는 두 선분이 없다는 것을 추측할 수 있었는데, 각 n의 값당 한 가지 경우만 있었고, 그 경우엔 항상 n개의 점들로 볼록다각형을 만들 수 있었어요.
(아래 문단은 추측인데, 정확한 증명은 표현하기 힘들어요. 아마도 다른 경우는 되지 않는다는 것을 증명하면 될 것 같아요. )
좋아요0 -
저도 선분들을 최대한 하나로 연결하는 경우를 고려해 봤는데,말이 쉽지 증명은 안되더라고요...
(현재 특정하게 오목 형태여도 간단한 범위 내에선 증명,n=4일땐 아시다시피 증명이 쉬운게 모양이 2개뿐이에요.)
좋아요0 -
@Funmaster
참고로 n=4일 때는 점들의 한 직선에 대한 위치 관계를 이용하여, 다른 점과 만나지 않는 선분이 두 쌍 있다는 것을 증명할 수 있어요.
좋아요0 -
네
좋아요0
-
-
-
-
-
-
확인요청중
위 풀이에선 간단할 줄 알았는데 하다 보니까 너무 복잡해진 것 같아요. 그래서 아이디어를 하나 더 냈어요.
I. [집합 X의 점이 n개일 때, n+1개의 선분을 그렸을 때 항상 만나지 않는 두 선분이 있다면, n+1보다 많은 선분을 그렸을 때 항상 만나지 않는 두 선분이 있다. ](선분을 더 그린다고 만나지 않던 선분이 만나게 되는 건 아니니까)
II. n+1개의 선분을 그릴 때, X의 모든 점이 적어도 한 선분의 끝점이 되게 그리는 경우만 증명하면 된다. 만약 임의의 점이 어떤 선분의 끝점도 되지 않았다면, 선분의 끝점이 된 점들만 모아 놓았을 때, 그 점의 개수+1보다 많은 개수의 선분을 그 점들에 그리게 되고, 그러면, [임의의 그래프의 모든 점이 적어도 한 선분의 끝점이 되게 그리는 경우를 증명했을 때, 이 경우에도 서로 만나지 않는 선분이 생기게 된다는 것을 증명할 수 있다(I에서). ]
이제부터 X의 모든 점이 적어도 한 선분의 끝점이 되게 그리는 경우만 생각하고, 또 X를 그래프라고 생각한다.
III. n+1개의 선분을 그렸을 때, 차수가 1인 점이 존재하지 않는 경우를 1번 경우, 차수가 1인 점이 존재하는 경우를 2번 경우라고 하자.
IV. 2번 경우에는, 임의의 차수가 1인 점을 제거하고, 그 점에 연결된 선분도 제거하면 점이 n-1개이고, 선분이 n개인 그래프가 만들어진다. 선분을 추가해도 만나지 않던 선분이 만나게 되는 것은 아니므로, 점이 n-1개일 때의 경우에서 항상 만나지 않는 선분이 생긴다는 것을 증명하면 2번 경우는 증명된다. 따라서, [1번 경우와 n=4일 때의 경우를 증명하면 전부 증명된다. ]
(용어 정의) 한 직선 위에 있지 않은 임의의 세 점 a,b,c에 대해, 반직선 (b,a)와 (b,c)는 공간을 두 부분으로 나누게 되는데, 그 두 부분 중 더 각이 작은 부분을 '(b->a,c) 안 공간'이라고 정의하자.
(용어 정의) 한 직선 위에 있지 않은 임의의 세 점 a,b,c에 때해, <(b->a,c) 안 공간의 임의의 점>과 <점 b>를 동시에 지나는 직선들의 집합을 '(b-a,c) 빨간 공간'이라 정의하자.
(용어 정의) 임의의 반직선 (a,b)에 대해, 직선 (a,b)에서 반직선 (a,b)를 제외한 도형을 반반직선 (a,b)라고 하자.
V. 다음 그림은 X의 임의의 점 a,b,c에 대해 '(b-a,c) 빨간 공간'을 빨간색으로 색칠한 그림이다.
이 (b-a,c) 빨간 부분에 임의의 점 p가 있다고 가정하고, 점 p와 연결된 선분에 대해 생각해 보면, 그래프 X의 모든 선분이 서로 만나게 하기 위해서는 점 p와 연결된 선분은 선분 (a,b)와 (b,c)에 동시에 만나야 한다. 선분(a,b)와 만나기 위해서는 점 p와 연결된 점은 (p->a,b) 안 공간에 있어야 하고, 선분 (b,c)와 만나기 위해서는 점 p와 연결된 점은 (p->b,c) 안 공간에 있어야 한다. 두 공간이 겹치는 부분은 반직선 (p,b) 뿐이고, 한 직선 위에 두 점밖에 있을 수 없으므로 그 점은 b이어야 한다. 따라서, 세 점 a,b,c가 (a,b)와 (b,c)로 연결되어 있다면, 그래프 X가 모든 선분이 서로 만나는 그래프이기 위해선 (b-a,c) 빨간 부분에 있는 점은 점 b와만 연결되어야 한다. (점 a,b는 제외) 그런데, 이때 빨간 부분에 있는 점이 점 b에만 연결되었다면, 그 차수는 1이게 되므로 이 경우는 2번 경우가 아니다. 그리고, 빨간 부분에 있는 점이 점 b에만 연결되지 않았다면 문제에서 주어진 명제는 성립한다. 따라서 [(a,b)와 (b,c)로 연결되어 있는 임의의 세 점 a,b,c에 대해 (b-a,c) 빨간 부분에 점이 없는 경우만 생각하면 된다. ]
VI. 임의의 차수가 3 이상인 점 p에 대해, p에 연결된 세 점 a,b,c를 생각할 수 있다. 이때, (p-a,b) 빨간 부분에는 점 c가 존재할 수 없으므로, 반반직선 (p,a) 위의 임의의 점 i와, 반반직선 (p,a) 위의 임의의 점 j에 대해 (p-a,j) 빨간 부분에 있어야 한다. 일반적으로 (p->a,j) 안 공간에 있다고 할 수도 있다. 이때, (p->c,b) 안 공간에 점 a가 있게 됨을 알 수 있다. 따라서, V에 의해 임의의 점의 차수가 3 이상인 경우는 생각하지 않아도 된다.
VII. 1번 경우에 속하는 그래프 X에서, 모든 점의 차수가 2라면 선분은 n개가 된다. 따라서 차수가 3인 점이 적어도 한 개는 존재하게 된다.
VIII. VI와 VII에 의해, 1번 경우는 모두 생각하지 않아도 됨을 알 수 있다. 여기서 1번 경우는 증명되었다.
XI. n=4일 때는, 선분이 끝점이 아닌 다른 점에서 만나는 경우는 최대 한 가지라는 것을 증명하는 것으로 해결할 수 있다. 4개의 점을 각각 1,2,3,4로 정하면, 끝점이 만나지 않는 선분 쌍은 ((1,2),(3,4)), ((1,3),(2,4)), ((1,4),(2,3))의 세 가지이다. 귀류법을 이용하기 위해, 이 중 만나는 선분 쌍이 두 가지(앞에 나열한 것 중 처음 두 가지)라고 가정한다. 그러면 점 3,4는 직선 (1,2)가 공간을 두 부분으로 나누었을 때 서로 다른 부분에 있어야 한다. 또, 점 2,4도 직선 (1,3)이 공간을 두 부분으로 나누었을 때 서로 다른 부분에 있어야 한다. 그러면, 직선(1,2)와 직선 (1,3)을 동시에 그린 형태를 생각해 보면, 공간이 나뉜 네 부분은 점 2,3과 동시에 맞닿는 곳, 점 1,2와만 맞닿는 곳, 점 1,3과만 맞닿는 곳, 점 1과만 맞닿는 곳으로 분류할 수 있는데, 점 4는 직선 (1,2)에 대해 생각했을 때 점 1과만 맞닿는 곳이나 점 1,2와만 맞닿는 곳에 있어야 하고, 직선 (1,3)에 대해 생각했을 때 점 1과만 맞닿는 곳이나 점 1,3과만 맞닿는 곳에 있어야 한다. 따라서 점 4는 점 1과만 맞닿는 곳에 있어야 한다. 그런데, 선분 (1,2)가 선분 (3,4)과 만나려면 직선 (1,3)과 직선 (3,2) 사이에 점 4가 있어야 하므로, 이때 선분 (1,2)와 선분 (3,4)는 만나지 않는다. 따라서 모순이고, n=4일 때 만나지 않는 선분 쌍은 최대 두 가지이다.
X. n=4일 때 선분은 최대 6개이고, 문제에서 선분을 5개 그린 것을 생각하므로, 선분을 6개 그린 형태에서 선분을 하나 제거하게 된다. 선분을 6개 그린 형태에서 만나지 않는 선분 쌍은 최소 두 개이므로(VI에서), 선분을 한 개를 제거해도 적어도 한 개의 만나지 않는 선분 쌍은 남는다. 따라서 n=4일 때도 증명된다.
IV에 의해, 전부 증명되었음을 알 수 있다.
