국가수리과학연구소의 27번째 문제입니다.
평면 위의 두 점을 이으면 선분을 만들 수 있다. 어떤 3개의 점도 한 직선 위에 있지 않도록 서로 다른 점 n개를 배치할 때, 점들이 만드는 선분 길이의 최소 가지 수는 얼마인가?
문제를 보자마자 떠오른 건 정n각형이네요.
정n각형은 어느 세점도 일직선상이 아닐뿐더러, 경우에 따라 길이가 같은 선분이 많기 때문입니다.
(정n각형이 최소라는 것은 추측입니다.)
그렇게 된다면 답은 이 되네요([]은 가우스 함수 표시입니다.)
우선 답은 이상임을 쉽게 증명할 수 있습니다.
특정 길이 에 대해
를 선분 길이로 가지는 점은
개 이하니까요.
우와 조합기하다! 내가 빠질 수 없지!
음 잠깐동안 생각을 해보았는데 다음과 같은 결과를 얻을 수 있었습니다. 우리가 구하려는 점들이 만드는 선분 길이의 최소 가지 수를 M이라고 하면
정n각형일 때의 예시가 있으므로 와 같이 M의 상한이 정해집니다.
다음 풀이는 M의 하한 대한 미완성된 증명입니다.
서로 다른 길이의 가짓수가 k가지라고 가정하자. 각각의 길이를 가지는 선분의 수를 개라고 하면, 총 선분의 수가
개이므로,
가 성립한다.
실수 s에 대하여, 길이 s을 가지는 선분이 x개라고 하자. 그러면 n개의 점을 꼭짓점으로 가지는 그래프에서 s만큼 떨어져 있는 두 점을 간선으로 잇자. 간선은 총 x개이므로, 각 점의 차수의 총합은 2x가 된다.
다시 차수가 y인 점 A를 보자. A로부터 s만큼 떨어진 점 두 개를 고르는 경우의 수는 가지이다. 이를 각 점에 대해서 생각한다. 각 점의 차수를
라고 하면, 점 A,B,C에 대해 AB=AC=s인 (A,B,C)의 순서쌍의 개수는
개이다. yC2는 y에 대한 이차함수이므로 아래로 볼록하고, 젠센 부등식에 의하여 최솟값을 가지는 때는
가 모두 같은 값을 가질 때이다. 따라서
가 성립한다.
이를 다른 선분길이들에 대해서 반복한다. 그러면 AB=AC인 (A,B,C)의 순서쌍의 개수의 하한을 도출할 수 있는데, 바로 가 된다. 이 식 역시 각 항이
에 대해 아래로 볼록하고,
이므로
이고,
까지 정리할 수 있다. 만약 여기서
이라면, AB=AC인 (A,B,C)의 순서쌍의 개수가
개보다 많게 되고, 비둘기집의 원리에 의해 어떤 두 점 X,Y가 존재해 XZ=YZ를 만족하는 Z가 세 개 이상 존재한다. 그들은 XY의 수직이등분선 위에 있으므로 세 점이 한 직선 위에 있게 되어 모순이다.☆ 따라서
이다.
이로써 가 증명되었다.
이 풀이의 완성, 즉 M이 와 같다는 것을 증명하려면 다음 단계가 필요하다. 위 볼드체로 표시된 문장 ☆은 다음을 의미한다. "n개의 점 중 두 개를 택하였을 때, 그 두 개의 수직이등분선 위에 있는 점의 개수의 평균값은 2 이하이다."
만약 평균값이 1 이하라는 것까지 증명을 할 수 있다면 가 성립하고, 즉
가 도출되고, 이는
과 동치이다.
n개의 점 중 두 개를 택하였을 때, 그 두개의 수직이등분선 위에 있는 점의 개수의 평균값은 항상 1 이하일까? 저는 여기서 더 진척을 이루지 못하겠군요. 이 과정을 여러분들에게 맡기겠습니다. 2주 후에까지 이 문제가 풀려있지 않다면, 남은 과정을 다시 도전하도록 하겠습니다.
음... 저는 아직 이 풀이를 제대로 이해하지 못했고, 그래서 수돌이 님의 가설을 제가 제대로 이해했는지는 모르겠습니다만,
만약 제 이해가 맞다면 아래와 같이 두 개의 정삼각형이 붙어 있을 경우 각 점들 사이 수직이등분선들 위의 점의 개수의 평균은 가 되어 1보다 커지지 않나요?
(사진이 좀 찌그러졌네요... 삼각형 ABC와 삼각형 ABD는 정삼각형입니다 -_-;;)
오 이런! 가설이 틀렸네요. 다른 방식으로 도전해야 겠군요. 하지만 평균값이 2 이하인 것은 사실이고, 제 방식으로는 (n-1)/3까지가 한계입니다...
아ㅠㅠ 가설이 틀린 게 맞군요.. 안타깝네요ㅠㅠ
+평균이 항상 2 이하인 건 자명한데, 이런 흥미로운 예시도 있더군요. 정확히 평균이 2가 됩니다. 평균의 상계는 더 이상 낮출 수가 없겠네요ㄷㄷ
(사각형 ABCD는 정사각형, 삼각형 ABF, BCG, CDH, DAE는 정삼각형)
DF같은 경우를 생각하면 더 작지 않나요? 평균의 상계가 더 작을 수도 있을 것 같습니다.
DF에 대해서는 점 E와 점 A가 수직이등분선 위에 있으므로 평균값의 상계는 2 이하로 줄일 수 없습니다.
저는 일단 n값이 작을 때 [n/2] 이하의 반례가 있는지 찾아보도록 하겠습니다. n=5까지는 반례가 없고 n=6일 때가 시간이 조금 걸리네요.
아니면 n에 대한 답을 f(n): N→Z 라고 정의할 때 f(n)이 단조증가함수임을 이용해도 되겠습니다. 만약 답이 정다각형일 때가 맞다면 n이 홀수일 때는 f(n) = f(n-1)이고, 짝수일 때만 변하겠죠. 여기서 수학적 귀납법으로 증명한다면 가능성이 있을 것 같습니다. 물론 반례가 없다는 가정 하에요.
20%짜리 증명
의 선분길이 가지수를 생각하자. 점이
개 일 때
개의 점으로 이루어진 모양이 분명히 포함되므로 점이
개 존재할 때 선분 길이의 최소 가지수를
라 하면
이다.
을 짝수로 두자. 1을 증가시켜도 정다각형을 생각하면
이므로
이 최소라면
도 최소이다.
은 홀수이다. 1을 증가시켰을 때 정다각형을 생각하면
이다. 증가값이 0일 수는 없으므로
이 최소라면
도 최소이다.
일 때, 1이 최소임이 자명하다. 따라서
이 선분 길이의 최소가지수이다.
어제부터 생각했는데 가장 중요한 빨간색 부분에서 막힙니다.
만약 답이 [n/2]인 예시 사이에 뚜렷한 규칙을 찾지 못한다면 이러한 방법은 힘들 것 같습니다. 정삼각형에 점 하나 추가해서 정사각형이 되는 게 아니니까요.
뭐, 정(n-1)각형의 중심에 점을 찍을 수 있긴 합니다. 점 개수가 짝수 개이면 이러한 방법이 통해요. 선분 길이의 가짓수가 최소인 배치를 모든 점들의 중심을 포함하고 있는 것과 포함하지 않는 것으로 나눈다면 어떨까요? 일대일 대응이 된다면 뭔가를 얻어낼 수 있을 것 같습니다.
정다각형에 점을 하나 추가해서 다시 정다각형을 만드는 것이 아니라, 최소한 점 n개로 이루어진 모양을 포함한다는 것을 말하고 싶었습니다. 그 모양의 선분길이 수가 최소 가지수 보다는 많거나 같을 거니까요.
문제는 짧기는 한데 수돌이님이나 아니면 tommy님의 풀이 보니까
그렇게 간단하지는 않을 것 같네요.
그나저나 문제가 오타있는 것 같은 것은 나만 그런건가?
왜 선분 길이의 최소 가지수이지?(그냥 선분의 개수라 해야 맞을것 같은데...)
문제 푸는데 별 도움은 안될 것같지만 '어떤 3개의 점도 한 직선 위에 있지 않도록' 이란 조건이 빠진다면 상한을 더 낮출 수 있을까요?
그런데 어떤 3개의 점도 한 직선 위에 있지 않도록 하려면 더 복잡해져서
어려울 것 같은데?
그렇다면 무조건 최소 길이 가지수가 1이 되지 않나요?
그렇네요. 그렇게 하면 너무 적어져서 또 문제네요.
어떻게 할 수 있나요? 점 4개만 되어도 가지수가 2개는 되야하지 않나요?
점이 이런( . . . .)식으로 있다면 두 번째와 네 번째 잇는 선도 고려하나요?
가지 수로 따지면 n개의 점을 일렬로 나열하면 n-1개의 가지수가 나옵니다.
아 잠깐 착각했네요. 죄송합니다.
상한은 낮아지고 문제는 어려워질 듯
그러니까 그냥 차라리 문제는 이 상태로 그대로 풀고
수학적귀납법으로 [n/2]인 것을 증명하면 될 것 같은데!
n=k일때에서 n=k+1로 넘어갈때!!!
k가 짝수일때와 홀수일때로 나눠서요.
일단 다들 [n/2]라는 것은 대충 나왔으니까......
일단 증명해야 할 명제는 '2n개의 점을 한 평면에 배치할 때, 선분 길이의 가짓수의 최솟값은 n개이다.' 로 바꿀 수 있을 것 같습니다.
위 명제를 증명하면 점의 개수가 2n+1개일 때는 최솟값이 n 이상인데, 정다각형인 경우의 값이 n이기 때문에 최솟값이 n이 됩니다.
그리고 이건 제 추측이지만, 세 점이 한 직선 위에 있어도 제가 제시한 명제는 성립할 것 같습니다.
삼차원 확장을 한 것도 답이 궁금하네요.
임의의 네 점이 한 평면 위에 존재하지 않으면서 거리의 최소 가짓수는 몇 개 일까요?
-망했어요
점 16개일 때 선분 길이의 가지수가 7개인 예시를 발견했습니다ㅜㅜ
결과는 다음과 같습니다.
네
이로써 세 점이 한 직선 위에 있지 않아야 한다는 조건이 없으면 길이의 최소 가짓수가 [n/2]가 아니라는 것이 보여졌네요.
하지만 세 점이 한 직선 위에 있지 않을 때는 저렇게 합동인 정삼각형을 붙이는 방법만으로 할 수 없어요. 제 생각에 이걸 이용해서 정다각형 또는 정다각형이 붙어있는 모양의 경우 하한이 [n/2]임을 먼저 보이면 도움이 될 것 같은데요.
먼저 위에서 정삼각형만이 붙어있는 경우 하한이 [n/2]라고 한것을 증명해 보자면, 정삼각형만이 배열되어 있을 때 모든 정삼각형이 변으로 붙어있다면 3개 붙일 때부터 이미 세 점이 한 직선 위에 있는 경우가 존재하므로 불가능합니다. 따라서 정삼각형이 꼭짓점으로 붙어있거나 붙어있지 않다고 해도 변으로는 2개씩밖에 붙어있을 수 없으므로 그 2개씩 붙은 조합들 사이의 거리에서 2개씩 붙은 모양을 이루는 네 점 중 두 점 이하만이 다른 한 점까지의 거리가 같을 수 있기 때문에 자명히 증명됩니다.
이와 같은 방법으로 생각하면 테셀레이션을 만드는 정다각형(삼각형, 사각형, 육각형)만을 붙인 형태에 대해서도 쉽게 하한이 [n/2]임을 증명할 수 있고, 아마도 서로 다른 정다각형들을 함께 모아 놓아도 하나의 정다각형으로 했을 때의 하한인 [n/2]보다 작은 거리의 개수가 나오지 않으리라 싶습니다. 그리고 그 후 정다각형 외의 다른 도형까지 사용했을 때 거리가 더 작아지지 않음을 보이기는 더 쉬우리라 생각합니다.
추상적이지만 증명을 해 보도록 하겠습니다.
먼저 점 n개가 여러 개의 정다각형만이 붙은 모양이라 가정하겠습니다.
이때 정다각형이 한 종류뿐이라면 테셀레이션 도형(정삼각형, 정사각형, 정육각형) 으로 나눌 수 있는데, 테셀레이션 도형 중 정삼각형은 최대 2개, 정사각형과 정육각형은 하나씩만 변으로 붙어 있을 수 있습니다. 따라서 이런 결합 구조가 여러 개 평면에 존재하는 모양이 되어야 하는데, 이렇게 결합 구조가 세 점이 한 직선 위에 있지 않도록 평면 위에 존재한다면 선분의 수직이등분선 위에 있는 점의 개수가 1 미만이 되므로 선분의 총 가짓수는 [n/2] 이상가 됩니다. 또한 테셀레이션 도형이 아닌 경우는 둘 이상의 도형이 붙을 때 각도가 달라지며 새로운 길이의 선분들이 생기므로 선분의 총 가짓수는 정다각형일 때 이상이 됩니다. 그러므로 정다각형이 한 종류뿐일 때는 선분의 최소 가짓수가 [n/2] 이상입니다.
여러 종류의 정다각형이 변으로 붙어 있는 경우를 생각하겠습니다. 서로 다른 두 정다각형이 붙는데 정육각형과 정삼각형이 붙는 것처럼 세 점이 한 선 위에 올라가지 않는 모든 경우에 대하여, 점 개수는 두 정다각형의 점 개수를 더한 것보다 두 개 적지만 선의 종류는 두 정다각형 각각의 선의 종류를 더한 것에서 1을 뺀 값보다 같거나 크게 되며 이므로 여러 종류의 정다각형을 붙인다고 해도 선분의 최소 가짓수는 [n/2] 이상입니다.
또한 정다각형들이 변으로 붙어 있지 않거나, 크기가 서로 다른 경우에서는 세 점이 한 직선 위에 있지 않다는 전제 하에, 점들 사이의 간격이 정다각형끼리 변으로 붙였을 때 생기는 간격의 종류보다 많아지므로 최소 가짓수가 [n/2] 이상이 됩니다.
마지막으로 정다각형 이외의 도형이 붙어 있거나, 정다각형 이외의 도형만으로 이루어진 도형을 생각하겠습니다. 이 도형에서 정다각형을 이루는 셋 이상의 점이 있다면 따로 떼어서 정다각형과 나머지 도형으로 나누는 과정을 가능한 한 많이 반복하여 더는 정다각형을 이루는 셋 이상의 점이 있지 않는 도형을 생각하겠습니다. 그러면 이 도형을 변의 길이의 가짓수와 대각선의 길이의 가짓수 모두, 정다각형에 비해 많거나 같게 됩니다. 이때 이 도형과 정다각형 또는 다른 도형을 붙일 때 어느 세 점도 한 직선 위에 있지 않다면 위에서와 같이 선분의 최소 가짓수가 [n/2] 이상입니다.
따라서 어느 경우든 선분의 길이의 최소 가짓수는 [n/2] 이상이고, 정다각형일 경우에서 어떤 n에 대해서라도 선분의 길이의 가짓수가 [n/2]가 될 수 있으므로 점들이 만드는 선분 길의의 최소 가짓수는 [n/2] 개입니다.