주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국17. 솔로몬의 직선

2018.05.01

같이 풀어볼까?

네이버밴드 구글플러스

 

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

 

평면 위에 점을 생각하자. 자연수 n에 대해, 한 평면 위에 총 2n개의 점이 있어 어떤 세 점도 한 직선 위에 없다고 하자. 만약 두 점을 이은 직선이 나머지 2n-2개의 점을 정확히 반반씩 나눈다면, 이 직선을 Halving line이라고 하자.

 

 

[문제]

 

문제1.

Halving line의 최소 개수는 얼마일까?

 

문제2.

Halving line의 최대 개수는 얼마일까?

(2-1) Halving line의 최대 개수가 어떤 고정된 상수 c>0에 대해 cn^{1.5} 이하임을 보여라.

(2-2) Halving line의 최대 개수가 어떤 고정된 상수 c>0에 대해 cn^{\frac{4}{3}} 이하임을 보여라.

(2-3) Halving line의 최대 개수의 상한을 더 줄일 수 있을까?

 

 

※문제 수정

(2-2)의 cn^{\frac{3}{4}}을 cn^{\frac{4}{3}}로 수정합니다! 

 

※알립니다

①1번 문제가 수학Poincaré12 친구에 의해 해결됐습니다! 2번 문제와 함께 1번의 다른 풀이 방법도 찾아보세요!!laugh

②풀이에 틀린 부분이 있는 경우 수정해서 다시 올리면 다른 친구들이 보고 이해하는 데 도움이 될 거예요! :)

③출제자 님과 상의한 결과, 문제2는 (2-1)만 풀어도 정답으로 인정하겠습니다~. 참고로 (2-2)는 한 논문에서 나온 결과고 (2-3)번은 누구도 답을 모르는 문제(open problem)이에요!

 

댓글 45

  • 구머 2018.05.01 18:37:45

    1번 답은 n개입니다.

    각 점마다 최소 1개의 halving line은 갖고 있을 것이니 전체 개수는 2n/2=n

    좋아요2 댓글수8
    • 수학장 2018.05.01 19:46:46

      각 점들이 오직 하나의 halving line만 가지게 할 수 있을까요?

      좋아요1
    • 구머 2018.05.01 20:46:54

      볼록2n각형으로 하면 될거에요.

      좋아요1
    • 김우현 기자 2018.05.02 11:45:36

      각 점이 왜 '최소 1개'의 halving line을 가지는지 좀더 구체적으로 설명해 줄 수 있나요?? surprise

      좋아요0
    • 수학장 2018.05.03 17:31:59

      임의의 고정된 점 하나를 선택해 봅시다.그 다음 다른 임의의 점을 또 선택한 후. 둘을 연결합니다. Halving line(h.l.이라고 하겠습니다)이 아니면, 바로 오른쪽에 있는 다른 점을 선택합니다. h.l.이 아니면 다시 반복합니다. 일직선상에 세 개의 점이 있기 때문에, 이 시행을 반복하면 적어도 한 개의 h.l이 있습니다

      좋아요0
    • 김우현 기자 2018.05.03 18:03:14

      '바로 오른쪽에 있는 다른 점을 선택합니다'만 좀더 자세히 설명해 주시면 좋을 것 같아요! 무엇을 기준으로 오른쪽인지.. 등이요!!laugh

      좋아요0
    • 수학장 2018.05.04 17:44:26

      가장 오른쪽에 있는 점은 시계 방향에서 전에 선택된 점, 고정된 점을 이은 선분과 이루는 각도가 가장 작은 직선을 말합니다

      좋아요0
    • 여백 패르마 2018.05.06 19:08:29

      예를 들자면 다음의 사진이 있습니다.

      다음의 사진의 회색 선은 다 halving line 입니다.

       

      좋아요0
    • 김우현 기자 2018.05.08 11:19:30

      백진언 연구원님의 말에 따르면, 그 직선이 halving line이라고 단정하려면 일직선 상에 세 개의 점이 있기 때문에보다 더 구체적인 설명과 논리가 필요하다고 해요!!smiley

      좋아요0
  • 화하학 2018.05.08 23:51:35

    1번의 정답은 n인 것 같습니다.

    일단 점이 적어도 한 개의 halving line을 갖는다는 것을 증명하겠습니다.

    일단 유사 halving line 에 대해 정의하도록 하겠습니다. 유사 halving line이란, 두점을 이은 직선이 나머지 2n-2개의 점을 n, n-2개로 나누는 직선입니다.

    만약 n=k일 때 점a와 점b를 잇는 halving line이 존재한다면, 유사 halving line은 halving line 으로 나누어진 각각의 면(하나는 x면, 하나는 y면) 에서 halving line과 가장 가까운 점 x,y(x는 x면에, y는 y면에 있음) 을 찾아 연결함으로써 점 a와 b당 각각 2개  만들 수 있습니다.

    n=k+1일 때, x면에 점 2개를 준다면, x와 이은 유사 halving line이 halving line으로 기능합니다. 

    y면에 점 2개를 준다면, y와 이은 유사 halving line이 halving line으로 기능합니다. 

    x면에 1개, y면에 1개를 준다면, 원래 halving line이 halving line으로 기능합니다.

    물론 halving line 위에 점을 올릴 가능성을 고려할 필요는 없고요.

    n=2일 때 점들이 halving line을 적어도 각각 1개 가지므로 점이 적어도 한 개의 halving line을 갖는다는 것을 증명했습니다.

    최소개수가 n일 때는 한 사분면안에만 있는 반비례 그래프 위에 점들을 배열하면 됩니다.

    좋아요0 댓글수3
    • 김우현 기자 2018.05.09 18:07:51

      백진언 연구원님의 한 마디!

      6번째 줄에 '점 a와 b당 각각 2개 만들 수 있습니다' 부분을 다시 한번 생각해 보세요! 잘 살펴보면 반례를 찾을 수 있습니다 :)

      좋아요0
    • 화하학 2018.05.20 21:00:00

      정다각형 내에 점이 하나 들어 있을 때만 반례가 성립하네요

      좋아요0
    • 출제자 2018.05.25 15:09:37

      출제자입니다. 문제 아이디어가 아닌 최종 풀이를 작성하실 때에는 풀이의 모든 과정이 엄밀하고 틀린 것 (예: 반례)이 없어야 합니다. 설사 풀이의 반례의 경우가 말씀하신 것처럼 많지 않더라 하더라도, 그런 반례밖에 없는지를 엄밀하게 설명할 수 있어야 완전한 풀이가 되기에, 아쉽게도 답으로 인정할 수 없음을 알려드립니다.

      좋아요0
  • Mathdragon 2018.05.16 00:30:05

    일단 Halving line이 n개이기 위해서는 모든 점들이 같은 원 위에 존재하면 되겠네요.

    2n개의 점이 있을 때 어느 점 하나를 잡고, 시계(또는 반시계)방향으로 n-1만큼 이동하여 그 점과 처음 잡은 원을 연결하여 직선을 그으면 그은 직선 위에는 반드시 n-1개의 점이 존재하게 되므로 Halving line이 됩니다.

    이와 같은 방법으로 n개의 점에 대하여 반복하면 모든 경우의 수를 찾을 수 있습니다.

    그 외의 경우에는 원에서 그은 직선 위(또는 아래)에n-1개 보다 적은 수의 점이 존재하게 되므로 다른 경우는 없음을 알 수 있습니다.

    이렇게 Halving line의 개수를 n개 까지는 줄일 수 있겠네요.

    그러면 이제 n개보다 더 줄일 수 있는지가 관건이겠죠,

    좋아요0 댓글수0
  • Poincaré12 2018.05.16 22:54:41

    우상 A2n-2-k-1

    우하2n-2+k

    1번 풀이입니다.

    아 2n-2-k가 아니라 n-1-k임니다

    2n-2+k가 아니라 n-1+k이고요.

    그러면 n-1+k=n(S0 U S1 U S2 U ... U Sn-1-k)<=n-3+k로 같은 모순이 생겨 본 증명의 결론은 보존됨니다.

     

     

    좋아요0 댓글수5
    • 수학장 2018.05.16 23:00:42

      2번이 어렵죠.... 2번은 정답이 알려져 있지도 않을 듯합니다.

      좋아요0
    • Poincaré12 2018.05.17 14:01:16

      그러게요 사실 저는 감도 안잡혀요 2번은 ㅠㅠ

      좋아요0
    • 김우현 기자 2018.05.21 17:29:24

      A_{i}와 n이 무엇을 뜻하는지와 A_{i}가 왜 오른쪽에만 있는지 등등 풀이에 쓰인 기호와 함수를 좀더 자세하게 설명해 줄 수 있나요??surprise

      좋아요0
    • Poincaré12 2018.05.21 21:18:22

      halving line을 가지지 않는 점을 p라함

      임의의 점 A0를 잡아 공간을 2등분 하고 그중 점의 개수가 더 적은 곳을 택하면 그공간에 있는 점의 개수는 임의의 자연수 k에 대해 n-1-k이다.

       그 공간에 있는 임의의 점 X에 대해 각A0 PX가 작은 것부터 차례대로 A, A, ... An-1-k  라한다.

      또 직선 Ap에 의해 반대편 공간이 나뉘는데 이떄 각자 나뉜 공간에 있는 점들의 집합을 각 A0 PS가 작은 순서대로 S1, S2, ... , Sn-1-k라 하고 특별이 직선A0P와 직선A1P사이에 있는 공간에 있는 점들의 집합을 S0라 한다.

       

      좋아요0
    • 김우현 기자 2018.05.23 14:44:32

      Poincaré12 친구도 정답!! 표기를 좀더 명확히 하면 좋을 것 같다는 의견입니다! 풀이는 Poincaré12 친구가 수학 친구보다 먼저 올렸으므로 1번 문제는 수학 친구와 Poincaré12 친구가 공동으로 푼 걸로 하겠습니다!!laugh

      좋아요0
  • 수학 2018.05.21 17:07:53

    임의의 하나의 점C를 잡습니다. 그리고 다른 하나의 점을 잡으고서 직선을 그읍니다. 그러면 선을 사이로 한쪽은 a개 다른한쪽은 b개가 있습니다.

    점C를 중심으로 시계 방향으로 회전 시켜나갑니다. 그러면 a와 b의 갯수가 변화되어집니다. 회전 시켜나가는 과정에서 점C가 다른 선과 직선을 

    이루는 때가 있는데, 그때마다 a가 +1혹은 -1변화되고, b는 -1혹은 +1변화 됩니다. 그 이유는 애초에 점 세개가 직선을 이루지 않으므로 직선에 한 점이

    빠지고 다른 점이 올라갈때마다 한개씩 변화해야 되기 때문입니다. 만약, 점 세개 이상이 직선을 이루면 2, 3, ...식으로 차이가 생길 수 있습니다.

    그런데, a, b의 갯수는 서로 반대가 될 수 있습니다. 처음에 a, b의 갯수가 정해져 있었는데, 점C가 중심이 되서 시계방향 회전하다가 180도 회전 후에는

    점C와 처음 연결되었던 점은 다시 연결되어 있지만, a, b,의 갯수가 반대가 됩니다. 그렇다면, a, b의 갯수가 1:1이었으면, C에 대한 하빙선이 있었다는 것이고, 

    그게 아니더라도, a, b는 반대가 되었고, 그 과정에서 1씩 변화 되었을 것이므로 중간에 a:b=1:1인 선이 있엇다는 것이 됩니다. 즉, 점 하나당 하빙선은 

    최소 한개씩 주어지게 됩니다. 그렇다면, 하빙선의 최솟값은 2n/2(2점이 한선을 만드므로 2로 나눔)보다 크거나 같게 됩니다.

    그렇다면, 2n개 점 중에서 한점을 중심에 두고, 나머지 홀수개 점을 180도 각도 사이에 같은 각도씩 나눠서 반원형으로 둥글게 배치 시킨 경우를 생각해 봅시다.

    이 경우는 시계 방향으로 회전 시켜 나가 보면 알지만 중앙 점에서도 하빙 점은 하나이고, 다른 점들에서도 하빙 점은 하나씩 밖에 없습니다. 즉, 이런 경우는 하빙 선이 정확히 n개

    가 됩니다. 최소한 하빙선은 n보다 이상이어야 되고, 하빙선이 n개인 경우가 반드시 있다는 점을 종합해보면 하빙선의 최소 갯수는 n개임을 알 수 있습니다.

    좋아요0 댓글수2
    • 김우현 기자 2018.05.21 18:07:09

      수학 친구, 정답입니다...! yes

      좋아요0
    • 수학 2018.05.21 18:48:56

      네 감사합니다

      좋아요0
  • Poincaré12 2018.05.21 21:39:51

    저 근데 2-2에서 n이 c^4보다 커지면 n>cn^0.75가 되어 최솟값이 최댓값보다 커지는데.... 머지요??

    좋아요0 댓글수1
    • 출제자 2018.05.25 15:10:27

      미안해요 ㅜㅜ 문제에 오타가 있었습니다. 문제가 수정되었으니 다시 확인해주세요!

      좋아요0
  • 수학 2018.05.22 13:33:50

    평면상에 점들이 있습니다. 그 때 점들은 두가지로 분류됩니다.

    경우1은 본 점과 다른 모든 점들이 180도 안에 연결선이 들어가는 경우의 점.

    경우2는 그렇지 않은 점.

    경우1의 경우 모두 외곽에 있을 점입니다. 이 점과 연결된 하빙선은 하나밖에 없습니다.

    총 하빙선 갯수가 n보다 커지려면 점 하나 당 하빙선이 2개 이상이어야 합니다. 최소값 증명에서 하빙선 최소값이 n이고, n인 이유가 점 하나 당 하빙선 1개가 최소이기 때문이라는 점을 알았기 때문입니다. 

    그런데 경우 1점들은 모두 하빙선 1개를 가지고 있습니다. 경우1의 점들이 홀수개면 하나 남기고 지우고 짝수개면 다 지웁니다. 그러면 지워진 점들은 2m개 입니다. 2n-2m개가 남게 됩니다.

    그러면 남은것들 중 하빙선이 n-m개 보다 커야지 맨 처음 점들 중 하빙선이 n보다 클 것입니다.

    그런데 이렇게 지우면 경우 1의 점들이 새로 생깁니다. 아까 처럼 지우는 작업을 계속이어서 해봅니다. 지우고 확인하고를 계속 수행하면 마지막에 경우 1인 점들만 짝수개 남습니다. 

    이경우 하빙선은 (남은 점들 갯수)/2개 입니다. 그렇다면 맨처음 점들도 하빙선은 n개라는 것이 됩니다.

    결국 최대값은 n이 됩니다.

    좋아요0 댓글수6
    • c언어 2018.05.22 18:43:07

      원위에 2n-1개의 점이 같은 간격으로 되어있고, 원의 중심에 하나의 점이 존재한다면 이때 원위의 각각의 점과 중간의 점은 연결하면 조건에 만족하는 선이 되기 때문에 2n-1개도 가능합니다.

      좋아요0
    • c언어 2018.05.22 18:46:01

      수학적으로 정의하기가 애매한 표현인데, 한 점을 기준으로 앞에만 다른 점이 존재한다면 그 점으로 이루어진 halving line은 1개이지만 한 점의 앞,뒤로 점이 존재한다면(원의 중심처럼)회전하면서 한쪽 점의 개수가 +1만 되는 것이 아니라 반대편에 의해 -1도 번갈아 되면서 한점에서 2개 이상의 halving line이 만들어 질 수 있습니다.

      좋아요0
    • 수학 2018.05.22 19:51:55

      c언어님 말대로 보니 두번째 풀이는 제가 잘못 풀은 부분이 있네요. 그런데 처음 풀이는 반박을 읽어봤는데 그렇게 점을 배치하면 세점이 한선에 있게되서 문제에 제시된 상황이 아니게 되지않을까요?

      좋아요0
    • c언어 2018.05.22 22:11:52

      점한개를 원의 중심에 배치하면, 원위에는 홀수개의 점이 위치해 있기 때문에 세 점이 한 직선 위에 있지는 않게 됩니다

       

      좋아요0
    • 김우현 기자 2018.05.23 09:34:12

      경우1은 본 점과 다른 모든 점들이 180도 안에 연결선이 들어가는 경우에서 '본 점'과 '180도 안에 연결선이 들어가는 경우'의 뜻을 좀더 자세히 설명해 줄 수 있나요??surprise c언어 친구는 이미 이해한 것 같지만..ㅜㅜ

      좋아요0
    • c언어 2018.05.23 17:59:00

      경우1은 본점과 다른 모든 점들이 180도 안에 연결선이 들어가는 경우 라는 말은 다른 방식으로 표현해 보겠습니다. 

      본점을 지나는 어떠한 직선이 평면을 두 부분으로 나누는데 두 부분중 한 부분에 점이 없는 경우가 생긴다면 경우1 이라고 할 수 있고,

      직선의 어떤 기울기 에서도 한 부분에 점이 1개이상 존재한다면 경우 2라고 할 수 있을것 같습니다.

      좋아요0
  • c언어 2018.05.22 18:58:44

    2-2 접근) 수학님의 댓글에 있는 것처럼 원위에 2n-1개의 점이 있고, 원의 중심에 1개의 점이 있다면

     halving line 은 2n-1개입니다. 이때 2-2의 식에 대입하면

    c{n}^{1.5}\geq{2n-1}이 되고 양변을 제곱해주면

    c^2n^3\geq 4n^2-4n+1이 됩니다. 

    c^2\geq \frac{4}{n} - \frac{4}{n^2}+ \frac{1}{n^3}이고, 우변의 그래프를 지오지브라를 통해서 그려보았습니다.

     이때 n의 값이 1일때는 1, 2일때는 9/8 그뒤에는 그래프와 같이 점점 작아지니 

    n이 자연수일때 우변의 값의 최대값은 9/8이 됩니다. 즉 c^2은 9/8 이상으로 

    c\geq \frac{3}{2^{\frac{1}{2}}}이 됩니다.

    좋아요0 댓글수0
  • c언어 2018.05.22 22:20:45

    halving line이 2n-1 인것은 나왔습니다. 지금 구한것은 n의 차수가 1이고, 2-3에서는 n의 차수가 3/4인데 차수가 더 작은 값 이하로 답이 나올 수가 있나요? n이 무한으로 가면 c의 값도 무한으로 발산할 것 같은데...

    좋아요0 댓글수1
    • 김우현 기자 2018.05.23 13:49:04

      문제에 오타가 있었네요!

      (2-2)의 cn^{\frac{3}{4}}을 cn^{\frac{4}{3}}로 수정합니다. 혼란스럽게 해서 죄송해요!!crying

      좋아요0
  • 수학 2018.05.23 18:14:07

    여기 그림을 보면 동그라미는 외곽의 점들을 연결하여 그렸다.

    그림1과 2는 하빙선의 교차점은 항상 동그라미 안에 있어야 됨을 보여준다. a+b=c와 a=b+c는 양립하지 않는다.

    그림 3, 4, 5 는 교차점이 모두 동그라미안에 있는 경우이다.

    그림4는 중심 하나에 모든 교차점이 있다. 만약 그렇게 안하면 그림3,5처럼 중심외의 다른 위치에 또 교차점을 그린다. 

    중심외에 교차점이 또 생기면 중심점 상하로 동일한 갯수의 점들이 있는데, 위의 점 위에 선을 그은 것이 되서 하빙선이 될 수 없다.(다음 댓글로 계속)

    좋아요0 댓글수3
    • 수학 2018.05.23 18:18:40

      그림 7과 같이 중심점을 기준으로 하빙선을 2n-1개 긋거나 중심에 점이 없이 하빙선을 그어 n개 긋는 것이 하빙선을 긋는 유일한 방법이 된다. 즉 최대값은 2n-1이다.

      좋아요0
    • 출제자 2018.05.25 15:19:01

      수학님,

      어떤 상수 C에 대해서도 Cn개 이상의 halving line을 만들 수 있음이 알려져 있습니다. 다시 한번 생각해보세요!

      좋아요0
    • 수학 2018.05.25 16:52:26

      네 알겠습니다

      좋아요0
  • c언어 2018.05.23 18:20:23

    2-3 접근(수학님이 최대값 풀이를 올려 주셨지만 아직 정답인지 확인이 않되서 접근으로 올립니다.)

     앞에 말한 것처럼 2n-1의 경우가 존재하므로 cn^{\frac{4}{3}}\geq 2n-1이 됩니다. 식을 정리하면

    c^3\geq \frac{8}{n}-\frac{12}{n^2}+\frac{6}{n^3}-\frac{1}{n^4}가 됩니다. 이번에도 그래프를 그려주면 

    n의 값이 정수일때 (2,27/16)이 최대값으로 c\geq \frac{3}{16^\frac{1}{3}}이 됩니다.

    좋아요0 댓글수1
    • 출제자 2018.05.25 15:18:02

      c언어님! 

      상수값에 대한 접근 잘 읽었습니다. 다만 문제에서 중점으로 두는 부분이 상수 c가 얼마나 큰지에 상관 없이, c가 존재하기만 하면 된다는 걸 말씀드리고 싶네요. 문제에서 중요한 부분중 하나는 halving line의 상한에서 n의 지수값을 최대한 작게 하는 것입니다. 이를테면 0.00001n^2이라는 상한과 10^{10} n^{1.5}라는 상한이 있다면, 비록 첫번째 상한이 상수가 매우 작더라도, n이 충분히 클 때 더 작은 상한은 두 번째 상한이 됩니다. 상수에 대한 탐구도 하나의 주제가 될 수 있지만, 문제에서는 상수가 얼마든지 커도 상관이 없습니다. 충분히 (10이던, 10만이던, 10억이던) 크다고 가정하고 푸셔도 좋아요!

      좋아요0
  • 정17각형 2018.06.20 18:52:54

    Halving line이 2n개인 경우를 찾았습니다.

     

    좋아요0 댓글수0
  • 수학장 2018.06.29 22:26:21

    만약 상한이 cn^2보다 작다는 것을 증명할 때

    모든 점들이 각각의 다른 점들과 이룬 직선들이 모두 n(2n-1)이므로 c가 2 이상이면 Halving line의 개수(H라고 합시다.)가 H<cn^2이므로 상한은cn^2보다 작다.

    이렇게 c를 맘대로 정의해도 되는 거죠?

    좋아요0 댓글수1
    • 정17각형 2018.07.31 13:34:15

      네 n의 차수만 비교하면 되고 c는 마음대로 정해도 됩니다. 

      좋아요0
  • 김우현 기자 2018.09.27 10:00:54

    출제자 님과 상의한 결과!

    (2-2)는 한 논문에서 나온 결과로 (2-1)과 내용이 비슷하고, (2-3)번은 누구도 답을 모르는 문제이므로 문제2는 (2-1)만 증명해도 푼 걸로 하겠습니다!surprise 

     

    좋아요0 댓글수0