본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[슬기로운 수학생활] 슬28. 만나지 않는 두 선분
수학동아 2022.08.01 11:05 조회 484

슬기로운 수학생활 28번

 

 

 

만나지 않는 두 선분

 

 

문제 출제자 : 백진언 미시간 대학교 수학과 박사과정생

 

 

 

 

 

평면에 n개의 점들이 있어서 어떤 세 점도 한 직선위에 없다. 이 점들의 집합을 X라 하자. 양 끝점이 X에 있는 서로 다른 n+1개의 선분들이 있다. 그러면 그 선분들 중에 두개의 서로 만나지 않는 선분이 있음을 보이자. 이때 서로 만나지 않는다는 것은 양 끝점을 포함해서 교차하는 점이 없다는 것이다.

 

 

 

백진언 연구원의 팁

 

힌트를 주면 핵심적인 부분이 전부 공개될 것 같다! 의외로 쉽지 않은 문제이지만 작은 예시들부터 시도해보면서 증명할 수 있는 성질들을 조금씩 찾아보자.

  •  
    Funmaster Lv.7 2022.08.01 13:46

    문제에 어느 세 점도 한 점 위에 있지 않은 건,n>=3이고,

    제가 잘못 이해한 거면 그럴 수 있지만,n=3일 때도 성립하는지가 확실하지 않네요.(제가 문제를 이해한 대로 하면요.)

     

    제가 이해한 것 중 잘못된 게 있나요?

    n개의 점이 집합 X에 속하고,어쨌든 양 끝점이 X에 속해 있는 선분 n+1개 중 서로 만나지 않는 선분이 있음을 보이라는 것인가요?

    댓글 작성하기 좋아요1 댓글수1
    •  
      출제자(슬기) Lv.4 2022.08.01 15:43

      n이 4 이상이라고 생각하시면 됩니다. X의 크기는 n이구요. n이 3이면 가능한 선분의 갯수가 3개기 때문에 서로 다른 4개의 선분이 있을 수가 없죠. 만약에 그런 선분들이 존재한다면 두개의 서로 만나는 선분이 있음을 보이라는 것이기 때문에, 명제 자체로는 n이 3일때도 성립합니다 ('가정이 거짓이면 명제가 참'으로 보통 얘기합니다 https://prudens-ripple.tistory.com/81). 다만 이게 헷갈리는 부분이기 때문에 조건에 n이 4 이상이라고 추가하는 것이 문제 이해에 도움이 될 것 같습니다.

      좋아요1
  •  
    다시 도전
    pure math Lv.7 2022.08.01 14:49

    댓글 작성하기 좋아요0 댓글수0
  •  
    다시 도전
    pure math Lv.7 2022.08.01 14:52

    댓글 작성하기 좋아요1 댓글수2
    •  
      출제자(슬기) Lv.4 2022.08.01 15:49

      '~~로 생각'이라는 애매한 표현보다 더 정확한 표현을 써주셨으면 좋겠습니다 (귀류법 가정을 적용한다거나, 무엇을 어떻게 생각한다는 건지가 말로 써져 있게요)

      P가 선분들의 집합인가요, 아니면 선분들 안에 있는 점들의 집합인가요? P랑 A의 교집합은 만약 P가 선분들의 집합이면 원칙적으로는 공집합입니다. P의 원소들은 선분인데 A의 원소들은 점이니까 둘이 다르지요. 만약 P가 선분들 안에 있는 점들의 집합이라면, P와 A의 교집합에는 경우 (한 선분이 한 점은 A에 있고 다른 점은 X'에 있음) 와 (한 선분이 두 점 모두 A에 있음) 을 구분해야 할 거 같습니다.

      좋아요1
    •  
      pure math Lv.7 2022.08.01 16:43

      아하 수정해서 올리겠습니다!

      좋아요0
  •  
    Funmaster Lv.7 2022.08.01 16:11

    그러면 n=7일 때, 이런 모양도 성립하나요? 실제 n=7일 때 사각형과 삼각형으로 따로 연결해 선분 8개를 그어 점들이 모두 서로 연결되지는 않는데,어쨌든 이러면 최소 만나지 않는 선분이 생깁니다. 이런 경우도 가능하다 하는 것이죠?

    댓글 작성하기 좋아요0 댓글수2
    •  
      출제자(슬기) Lv.4 2022.08.01 16:55

      생각하시는 예제를 정확히 이해한건진 모르겠는데, 아마 삼각형에서 선분하나 사각형에서 선분하나 이렇게 고르면 둘이 만나지 않을거에요. 점들이 모두 서로 연결될 필요는 없습니다.

      좋아요0
    •  
      Funmaster Lv.7 2022.08.01 17:00

      넵!(바로 그 답을 원했습니다.)

      좋아요0
  •  
    Funmaster Lv.7 2022.08.01 19:49 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    Amath Lv.8 2022.08.01 22:18 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    Funmaster Lv.7 2022.08.01 23:41

    n개의 점을 찍어 그 모양이 볼록 다각형이면 저는 어느 정도 증명할 수 있는데,다른 모양까지 고려하니 간단하진 않네요..

    볼록 다각형이 되면 일단 선분을 그어 n개의 선분을 완성 시킨 뒤,대각선을 하나 긋는 방식이 되는데,이때 대각선 이외로 한 선분당 만나지 않는 선분이 1개 이상으로 여러 쌍인 건 아는데,이건 그 점을 정확히 볼록다각형으로 연결시키는 경우만 성립해서...(심지어 그 점을 잘 연결시킬 때,볼록다각형으로 나오지 않아도 방법이 있는데,그걸 증명하는 것은 간단하지가 않네요.)

    댓글 작성하기 좋아요0 댓글수4
    •  
      Amath Lv.8 2022.08.03 10:22

      저는 지금까지 (형태가 다각형이라는 거지, 선분이 서로 만날 수도 있음. 다각형을 꼬아 놓은 형태도 될 수 있음. )다각형 형태로 n개의 선분을 연결할 때, 거기에 선분 한 개만 추가해도 만나지 않는 선분이 생긴다는 것을 증명하면 전부 증명된다는 것을 알아냈어요. 

       

      그리고 최대한 선분을 전부 만나게 하려고 해 보니, 특정한 형태에서만 만나지 않는 두 선분이 없다는 것을 추측할 수 있었는데, 각 n의 값당 한 가지 경우만 있었고, 그 경우엔 항상 n개의 점들로 볼록다각형을 만들 수 있었어요. 

       

      (아래 문단은 추측인데, 정확한 증명은 표현하기 힘들어요. 아마도 다른 경우는 되지 않는다는 것을 증명하면 될 것 같아요. )

      좋아요0
    •  
      Funmaster Lv.7 2022.08.03 14:45

      저도 선분들을 최대한 하나로 연결하는 경우를 고려해 봤는데,말이 쉽지 증명은 안되더라고요...

      (현재 특정하게 오목 형태여도 간단한 범위 내에선 증명,n=4일땐 아시다시피 증명이 쉬운게 모양이 2개뿐이에요.)

      좋아요0
    •  
      Amath Lv.8 2022.08.04 16:16

      @Funmaster

       

      참고로 n=4일 때는 점들의 한 직선에 대한 위치 관계를 이용하여, 다른 점과 만나지 않는 선분이 두 쌍 있다는 것을 증명할 수 있어요. 

      좋아요0
    •  
      Funmaster Lv.7 2022.08.04 17:10

      좋아요0
  •  
    pure math Lv.7 2022.08.07 20:58 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    수학잘하고싶다 Lv.2 2022.08.12 01:28 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911