폴리매스

역대 문제중 제일 짧은 것 같네요.

문제를 보자마자 떠오른 건 정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주 후에까지 이 문제가 풀려있지 않다면, 남은 과정을 다시 도전하도록 하겠습니다.

저는 일단 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이 최소임이 자명하다. 따라서 이 선분 길이의 최소가지수이다.

어제부터 생각했는데 가장 중요한 빨간색 부분에서 막힙니다.

문제는 짧기는 한데 수돌이님이나 아니면 tommy님의 풀이 보니까

그렇게 간단하지는 않을 것 같네요.

그나저나 문제가 오타있는 것 같은 것은 나만 그런건가?

왜 선분 길이의 최소 가지수이지?(그냥 선분의 개수라 해야 맞을것 같은데...)

만약 [n/2]이 맞다면 상한을 더 줄이는 것보다는 하한을 높이는 시도를 해야 합니다.

문제 푸는데 별 도움은 안될 것같지만 '어떤 3개의 점도 한 직선 위에 있지 않도록' 이란 조건이 빠진다면 상한을 더 낮출 수 있을까요? 

그러니까 그냥 차라리 문제는 이 상태로 그대로 풀고

수학적귀납법으로 [n/2]인 것을 증명하면 될 것 같은데!

n=k일때에서 n=k+1로 넘어갈때!!!

k가 짝수일때와 홀수일때로 나눠서요.

일단 다들 [n/2]라는 것은 대충 나왔으니까......

​​​​일단 증명해야 할 명제는 '2n개의​​​​​​ 점을 한 평면에 배치할 때, 선분 길이의 가짓수의 최솟값은 n개이다.' 로 바꿀 수 있을 것 같습니다. 

위 명제를 증명하면 점의 개수가 2n+1개일 때는 최솟값이 n 이상인데, 정다각형인 경우의 값이 n이기 때문에 최솟값이 n이 됩니다.

그리고 이건 제 추측이지만, 세 점이 한 직선 위에 있어도 제가 제시한 명제는 성립할 것 같습니다.

​​​​​​

삼차원 확장을 한 것도 답이 궁금하네요.

임의의 네 점이 한 평면 위에 존재하지 않으면서 거리의 최소 가짓수는 몇 개 일까요?

-망했어요

점 16개일 때 선분 길이의 가지수가 7개인 예시를 발견했습니다ㅜㅜ 

결과는 다음과 같습니다.

추상적이지만 증명을 해 보도록 하겠습니다.

먼저 점 n개가 여러 개의 정다각형만이 붙은 모양이라 가정하겠습니다.

이때 정다각형이 한 종류뿐이라면 테셀레이션 도형(정삼각형, 정사각형, 정육각형) 으로 나눌 수 있는데, 테셀레이션 도형 중 정삼각형은 최대 2개, 정사각형과 정육각형은 하나씩만 변으로 붙어 있을 수 있습니다. 따라서 이런 결합 구조가 여러 개 평면에 존재하는 모양이 되어야 하는데, 이렇게 결합 구조가 세 점이 한 직선 위에 있지 않도록 평면 위에 존재한다면 선분의 수직이등분선 위에 있는 점의 개수가 1 미만이 되므로 선분의 총 가짓수는 [n/2] 이상가 됩니다. 또한 테셀레이션 도형이 아닌 경우는 둘 이상의 도형이 붙을 때 각도가 달라지며 새로운 길이의 선분들이 생기므로 선분의 총 가짓수는 정다각형일 때 이상이 됩니다. 그러므로 정다각형이 한 종류뿐일 때는 선분의 최소 가짓수가 [n/2] 이상입니다.

여러 종류의 정다각형이 변으로 붙어 있는 경우를 생각하겠습니다. 서로 다른 두 정다각형이 붙는데 정육각형과 정삼각형이 붙는 것처럼 세 점이 한 선 위에 올라가지 않는 모든 경우에 대하여, 점 개수는 두 정다각형의 점 개수를 더한 것보다 두 개 적지만 선의 종류는 두 정다각형 각각의 선의 종류를 더한 것에서 1을 뺀 값보다 같거나 크게 되며  이므로 여러 종류의 정다각형을 붙인다고 해도 선분의 최소 가짓수는 [n/2] 이상입니다.

또한 정다각형들이 변으로 붙어 있지 않거나, 크기가 서로 다른 경우에서는 세 점이 한 직선 위에 있지 않다는 전제 하에, 점들 사이의 간격이 정다각형끼리 변으로 붙였을 때 생기는 간격의 종류보다 많아지므로 최소 가짓수가 [n/2] 이상이 됩니다.

마지막으로 정다각형 이외의 도형이 붙어 있거나, 정다각형 이외의 도형만으로 이루어진 도형을 생각하겠습니다. 이 도형에서 정다각형을 이루는 셋 이상의 점이 있다면 따로 떼어서 정다각형과 나머지 도형으로 나누는 과정을 가능한 한 많이 반복하여 더는 정다각형을 이루는 셋 이상의 점이 있지 않는 도형을 생각하겠습니다. 그러면 이 도형을 변의 길이의 가짓수와 대각선의 길이의 가짓수 모두, 정다각형에 비해 많거나 같게 됩니다. 이때 이 도형과 정다각형 또는 다른 도형을 붙일 때 어느 세 점도 한 직선 위에 있지 않다면 위에서와 같이 선분의 최소 가짓수가 [n/2] 이상입니다.

따라서 어느 경우든 선분의 길이의 최소 가짓수는 [n/2] 이상이고, 정다각형일 경우에서 어떤 n에 대해서라도 선분의 길이의 가짓수가 [n/2]가 될 수 있으므로 점들이 만드는 선분 길의의 최소 가짓수는 [n/2] 개입니다.