본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[폴리매스 문제] 국27. 점들의 이유있는 밀당
수학동아 2019.03.01

 

국가수리과학연구소의 27번째 문제입니다.

 

평면 위의 두 점을 이으면 선분을 만들 수 있다. 어떤 3개의 점도 한 직선 위에 있지 않도록 서로 다른 점 n개를 배치할 때, 점들이 만드는 선분 길이의 최소 가지 수는 얼마인가?

 

 

  •  
    21세기오일러 Lv.9 2019.03.01

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    code Lv.3 2019.03.01

    문제를 보자마자 떠오른 건 정n각형이네요.

    정n각형은 어느 세점도 일직선상이 아닐뿐더러, 경우에 따라 길이가 같은 선분이 많기 때문입니다.

    (정n각형이 최소라는 것은 추측입니다.)

    그렇게 된다면 답은 [\frac{n}{2}]이 되네요([]은 가우스 함수 표시입니다.)

    댓글 작성하기 좋아요0 댓글수2
    •  
      인천 오일러 Lv.1 2019.03.01

       저도 정다각형을 떠올렸습니다.  부연설명으로 정n각형의 대각선 길이의 개수는 한 꼭짓점에서 몇 칸 떨어진 점을 연결했는가를 생각하면 n이 짝수일때 0,1,2,...\frac{n}{2}...1,0 이므로 겹치는 것과 0,1을 제외하면 \frac{n-2}{2}개 가 되어 총 길이 개수는 \frac{n}{2}개 입니다. 그리고 n이 홀수이면  대각선 길이 종류가 \frac{n-3}{2}개가 되어 총 \frac{n-1}{2}개 입니다. 합쳐서 표현하면 code 님께서 제시한 [\frac{n}{2}]입니다.

      좋아요0
    •  
      아인수타인 Lv.8 2019.03.02

      저도 그거 생각했는데 이미 올라와 있었네요. (이번 건 그래도 풀만한 거 같습니다.)

      좋아요0
  •  
    79brue Lv.5 2019.03.01

    우선 답은 \frac{n-1}{4\sqrt{n}} 이상임을 쉽게 증명할 수 있습니다.

    특정 길이 x에 대해 x를 선분 길이로 가지는 점은 2n\sqrt{n}개 이하니까요.

    댓글 작성하기 좋아요0 댓글수1
  •  
    수돌이 Lv.2 2019.03.02

    우와 조합기하다! 내가 빠질 수 없지!

    음 잠깐동안 생각을 해보았는데 다음과 같은 결과를 얻을 수 있었습니다. 우리가 구하려는 점들이 만드는 선분 길이의 최소 가지 수를 M이라고 하면

    정n각형일 때의 예시가 있으므로 [\frac{n}{2}] \geq M와 같이 M의 상한이 정해집니다.

    다음 풀이는 M의 하한 M\geq \frac{n-1}{3} 대한 미완성된 증명입니다.

    서로 다른 길이의 가짓수가 k가지라고 가정하자. 각각의 길이를 가지는 선분의 수를 x_1, x_2, ...,x_{k}개라고 하면, 총 선분의 수가 \binom{n}{2}개이므로, x_1+x_2+...+x_k=\binom{n}{2}가 성립한다.

    실수 s에 대하여, 길이 s을 가지는 선분이 x개라고 하자. 그러면 n개의 점을 꼭짓점으로 가지는 그래프에서 s만큼 떨어져 있는 두 점을 간선으로 잇자. 간선은 총 x개이므로, 각 점의 차수의 총합은 2x가 된다.

    다시 차수가 y인 점 A를 보자. A로부터 s만큼 떨어진 점 두 개를 고르는 경우의 수는 \binom{y}{2}가지이다. 이를 각 점에 대해서 생각한다. 각 점의 차수를 y_1, y_2, ...,y_{n}라고 하면, 점 A,B,C에 대해 AB=AC=s인 (A,B,C)의 순서쌍의 개수는 \binom{y_1}{2}+\binom{y_2}{2}+...+\binom{y_{n}}{2}개이다. yC2는 y에 대한 이차함수이므로 아래로 볼록하고, 젠센 부등식에 의하여 최솟값을 가지는 때는 y_1, y_2, ...,y_{n}가 모두 같은 값을 가질 때이다. 따라서\binom{y_1}{2}+\binom{y_2}{2}+...+\binom{y_{n}}{2} \geq n\frac{(\frac{2x}{n})(\frac{2x}{n}-1)}{2}가 성립한다.

    이를 다른 선분길이들에 대해서 반복한다. 그러면 AB=AC인 (A,B,C)의 순서쌍의 개수의 하한을 도출할 수 있는데, 바로 \sum_{i=1}^{k} n\frac{(\frac{2x_i}{n})(\frac{2x_i}{n}-1)}{2}가 된다. 이 식 역시 각 항이 x_i에 대해 아래로 볼록하고, x_1+x_2+...+x_k=\binom{n}{2}이므로 \sum_{i=1}^{k} n\frac{(\frac{2x_i}{n})(\frac{2x_i}{n}-1)}{2} \geq nk\frac{(\frac{2\binom{n}{2}}{nk})(\frac{2\binom{n}{2}}{nk}-1)}{2}이고,

    nk\frac{(\frac{2\binom{n}{2}}{nk})(\frac{2\binom{n}{2}}{nk}-1)}{2} = nk\frac{(\frac{n-1}{k})(\frac{n-1}{k}-1)}{2}=\frac{n(n-1)(n-1-k)}{2k}=\binom{n}{2}\frac{n-1-k}{k}까지 정리할 수 있다. 만약 여기서 k<\frac{n-1}{3}이라면, AB=AC인 (A,B,C)의 순서쌍의 개수가 2\binom{n}{2}개보다 많게 되고, 비둘기집의 원리에 의해 어떤 두 점 X,Y가 존재해 XZ=YZ를 만족하는 Z가 세 개 이상 존재한다. 그들은 XY의 수직이등분선 위에 있으므로 세 점이 한 직선 위에 있게 되어 모순이다.☆ 따라서 k\geq \frac{n-1}{3}이다.

    이로써 [\frac{n}{2}]\geq M\geq \frac{n-1}{3}가 증명되었다.

    이 풀이의 완성, 즉 M이 [\frac{n}{2}]와 같다는 것을 증명하려면 다음 단계가 필요하다. 위 볼드체로 표시된 문장 ☆은 다음을 의미한다. "n개의 점 중 두 개를 택하였을 때, 그 두 개의 수직이등분선 위에 있는 점의 개수의 평균값은 2 이하이다."

    만약 평균값이 1 이하라는 것까지 증명을 할 수 있다면 \frac{n-1-k}{k}\leq 1가 성립하고, 즉 n-1\leq 2k가 도출되고, 이는 [\frac{n}{2}]\leq k과 동치이다.

    n개의 점 중 두 개를 택하였을 때, 그 두개의 수직이등분선 위에 있는 점의 개수의 평균값은 항상 1 이하일까? 저는 여기서 더 진척을 이루지 못하겠군요. 이 과정을 여러분들에게 맡기겠습니다. 2주 후에까지 이 문제가 풀려있지 않다면, 남은 과정을 다시 도전하도록 하겠습니다.

    댓글 작성하기 좋아요1 댓글수4
    •  
      tommy Lv.1 2019.03.02

      음... 저는 아직 이 풀이를 제대로 이해하지 못했고, 그래서 수돌이 님의 가설을 제가 제대로 이해했는지는 모르겠습니다만,

      만약 제 이해가 맞다면 아래와 같이 두 개의 정삼각형이 붙어 있을 경우 각 점들 사이 수직이등분선들 위의 점의 개수의 평균은 \frac{2+2+1+1+1+1}{6}=\frac{4}{3}가 되어 1보다 커지지 않나요?

      (사진이 좀 찌그러졌네요... 삼각형 ABC와 삼각형 ABD는 정삼각형입니다 -_-;;)

      좋아요0
    •  
      수돌이 Lv.2 2019.03.02

      오 이런! 가설이 틀렸네요. 다른 방식으로 도전해야 겠군요. 하지만 평균값이 2 이하인 것은 사실이고, 제 방식으로는 (n-1)/3까지가 한계입니다...

      좋아요0
    •  
      tommy Lv.1 2019.03.02

      아ㅠㅠ 가설이 틀린 게 맞군요.. 안타깝네요ㅠㅠ

      +평균이 항상 2 이하인 건 자명한데, 이런 흥미로운 예시도 있더군요. 정확히 평균이 2가 됩니다. 평균의 상계는 더 이상 낮출 수가 없겠네요ㄷㄷ

      (사각형 ABCD는 정사각형, 삼각형 ABF, BCG, CDH, DAE는 정삼각형)

      좋아요0
    •  
      디듀우 Lv.6 2019.03.23

      DF같은 경우를 생각하면 더 작지 않나요? 평균의 상계가 더 작을 수도 있을 것 같습니다.

      좋아요0
  •  
    79brue Lv.5 2019.03.02

    저는 일단 n값이 작을 때 [n/2] 이하의 반례가 있는지 찾아보도록 하겠습니다. n=5까지는 반례가 없고 n=6일 때가 시간이 조금 걸리네요.

    댓글 작성하기 좋아요0 댓글수0
  •  
    79brue Lv.5 2019.03.02

    아니면 n에 대한 답을 f(n): N→Z 라고 정의할 때 f(n)이 단조증가함수임을 이용해도 되겠습니다. 만약 답이 정다각형일 때가 맞다면 n이 홀수일 때는 f(n) = f(n-1)이고, 짝수일 때만 변하겠죠. 여기서 수학적 귀납법으로 증명한다면 가능성이 있을 것 같습니다. 물론 반례가 없다는 가정 하에요.

    댓글 작성하기 좋아요0 댓글수1
    •  
      인천 오일러 Lv.1 2019.03.02

      저도 생각했는데 ,한 부분이 막히네요 ㅠㅠ

      좋아요0
  •  
    인천 오일러 Lv.1 2019.03.02

     20%짜리 증명 

     

     n+1의 선분길이 가지수를 생각하자. 점이 n+1개 일 때 n개의 점으로 이루어진 모양이 분명히 포함되므로 점이 x개 존재할 때 선분 길이의 최소 가지수를 f(x)라 하면 f(x+1) \geq f(x)이다. 

    n을 짝수로 두자. 1을 증가시켜도 정다각형을 생각하면 f(n)=f(n+1)이므로 f(n)이 최소라면 f(n+1)도 최소이다. 

    n-1은 홀수이다. 1을 증가시켰을 때 정다각형을 생각하면 f(n)=f(n-1)+1이다. 증가값이 0일 수는 없으므로 f(n-1)이 최소라면 f(n)도 최소이다.

     n=3일 때, 1이 최소임이 자명하다. 따라서 [\frac{n}{2}]이 선분 길이의 최소가지수이다.

     

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

     

     

    댓글 작성하기 좋아요0 댓글수3
    •  
      79brue Lv.5 2019.03.02

      만약 답이 [n/2]인 예시 사이에 뚜렷한 규칙을 찾지 못한다면 이러한 방법은 힘들 것 같습니다. 정삼각형에 점 하나 추가해서 정사각형이 되는 게 아니니까요.

      좋아요0
    •  
      79brue Lv.5 2019.03.02

      뭐, 정(n-1)각형의 중심에 점을 찍을 수 있긴 합니다. 점 개수가 짝수 개이면 이러한 방법이 통해요. 선분 길이의 가짓수가 최소인 배치를 모든 점들의 중심을 포함하고 있는 것과 포함하지 않는 것으로 나눈다면 어떨까요? 일대일 대응이 된다면 뭔가를 얻어낼 수 있을 것 같습니다.

      좋아요0
    •  
      인천 오일러 Lv.1 2019.03.02

       정다각형에 점을 하나 추가해서 다시 정다각형을 만드는 것이 아니라, 최소한 점 n개로 이루어진 모양을 포함한다는 것을 말하고 싶었습니다. 그 모양의 선분길이 수가 최소 가지수 보다는 많거나 같을 거니까요.

      좋아요0
  •  
    sincostan Lv.6 2019.03.02

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

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

    댓글 작성하기 좋아요0 댓글수4
    •  
      sincostan Lv.6 2019.03.02

      그런데 답은 [n/2]인 것 같네요.(저도 찾고 있어요.)

      좋아요0
    •  
      79brue Lv.5 2019.03.02

      n=6까지는 반례가 없음을 증명하였습니다.

      증명은 그냥 모든 경우 다 해 보면 되므로 생략.

      좋아요0
    •  
      아인수타인 Lv.8 2019.03.02

      모든 경우요...? 점이 있을 수 있는 위치 자체가 무한한데 어떻게 그러지...?

      좋아요0
    •  
      B.C.I.수학장 Lv.5 2019.03.02

      두 개의 점의 수직이등분선 위에 있는 점의 개수의 평균값이 1 이상인 경우들만 하면 됩니다. 평균값이 1 이하인 경우에는 수돌이님이 증명했으니까요.

      좋아요0
  •  
    sincostan Lv.6 2019.03.02

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

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

    댓글 작성하기 좋아요0 댓글수3
    •  
      B.C.I.수학장 Lv.5 2019.03.02

      선분 길이의 최소 개수 맞습니다. 그니까 같은 길이의 선분들은 1가지로 세는 겁니다.

      좋아요0
    •  
      아인수타인 Lv.8 2019.03.02

      선분이 무한하다 해도, 모두 길이가 같으면 1가지로 칩니다.

      좋아요0
    •  
      79brue Lv.5 2019.03.02

      n=7일 때까지에 대한 증명을 첨부하겠습니다.

       

      여기를 누르세요.

      좋아요0
  •  
    B.C.I.수학장 Lv.5 2019.03.02

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    누군가 Lv.1 2019.03.04

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

    댓글 작성하기 좋아요0 댓글수8
    •  
      sincostan Lv.6 2019.03.04

      그런데 어떤 3개의 점도 한 직선 위에 있지 않도록 하려면 더 복잡해져서

      어려울 것 같은데?

      좋아요0
    •  
      인천 오일러 Lv.1 2019.03.04

       그렇다면 무조건 최소 길이 가지수가 1이 되지 않나요?

      좋아요0
    •  
      sincostan Lv.6 2019.03.04

      그렇네요. 그렇게 하면 너무 적어져서 또 문제네요.

      좋아요0
    •  
      누군가 Lv.1 2019.03.04

      어떻게 할 수 있나요? 점 4개만 되어도 가지수가 2개는 되야하지 않나요?

      좋아요0
    •  
      아인수타인 Lv.8 2019.03.05

      점이 이런( .    .    .    .)식으로 있다면 두 번째와 네 번째 잇는 선도 고려하나요?

      좋아요0
    •  
      누군가 Lv.1 2019.03.05

      가지 수로 따지면 n개의 점을 일렬로 나열하면 n-1개의 가지수가 나옵니다.

      좋아요0
    •  
      인천 오일러 Lv.1 2019.03.05

       아 잠깐 착각했네요. 죄송합니다.

      좋아요0
    •  
      B.C.I.수학장 Lv.5 2019.03.05

      상한은 낮아지고 문제는 어려워질 듯

      좋아요0
  •  
    sincostan Lv.6 2019.03.05

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

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

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

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

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    surkitz Lv.1 2019.03.10

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

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

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

    ​​​​​​

     

    댓글 작성하기 좋아요0 댓글수1
    •  
      페르마 Lv.1 2019.03.17

      그런데 제가 문제를 잘이해한 게 아닐 수도 있지만 그러한 명제가 성립된다면 문제에 그ㅡ런 조건이 있지 않을가요????

      그리고 애초에 n/2이 아닐 수 있는 것 아닌가요?? 왜 가설이 그렇죠???

      좋아요0
  •  
    Undefined Lv.1 2019.05.31

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

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

    f(1)=0,f(2)=1,f(3)=1

    f(4)=1

    f(8)=3

    댓글 작성하기 좋아요0 댓글수0