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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대21. 공간에서 교집합 찾기

2018.09.03

같이 풀어볼까?

네이버밴드 구글플러스

대한수학회 9월 문제는 볼록 기하학에 관한 겁니다. 어떤 볼록 집합들의 교집합이 존재한다는 건 라돈의 정리를 활용하면 증명할 수 있습니다. 라돈의 정리를 쓰지 않고 증명해보는 것도 의미가 있을 것 같아 이번 문제를 출제합니다.

 

볼록기하학(convex geometry)이란, 유클리드 공간에서 볼록 집합이 가지는 성질을 연구하는 기하학이다.

가령 평면 위에 점이 4개인 집합이 있다고 하자. 각 점을 2가지 색으로 잘 색칠해 각 색의 볼록 폐포(Convex closure)가 서로 만나도록 만들 수 있다. 이를 일반화한 것이 라돈의 정리다.

★볼록 폐포: 주어진 점이나 영역을 포함하는 가장 작은 볼록 집합을 말한다. 집합 안의 임의의 두 점을 골랐을 때 둘을 연결하는 선분이 집합 안에 속하면 볼록 집합이라고 한다.

 

점이 4개일 때 위의 조건에 맞게 나타내면 반드시 둘 중 하나가 된다.

 

※라돈의 정리

d차원 유클리드 공간 \mathbb{R}^d에 있는 d+2개의 점의 집합 \left \{x_1, x_2, \cdots, x_{d+2} \right \}에 대해서도, 볼록 폐포가 교차하는 두 부분 집합으로 분할할 수 있다.

 

 

문제1

라돈의 정리를 증명하여라.

 

 

문제2

일곱 개의 점 x_1, x_2, \cdots, x_7이 3차원 공간 위에 있다. 점 x_1은 세 점 x_4, x_6, x_7을 꼭짓점으로 하는 삼각형 내부에 있다. 또한 점 x_5x_2\large x_4을 잇는 선분 위에 있고, 점 x_6x_3x_5를 잇는 선분 위에 있다. 네 개의 사면체 A, B, C, D의 꼭짓점이 다음과 같을 때, A\cap B \cap C \cap D는 어떤 사면체를 반드시 포함함을 증명하여라.

    A의 꼭짓점 : x_4, x_5, x_6, x_7
    B의 꼭짓점 : x_1, x_2, x_3, x_6
    C의 꼭짓점 : x_1, x_2, x_6, x_7
    D의 꼭짓점 : x_1, x_5, x_6, x_7

 

※오타를 수정합니다.

문제2 2번째 줄에 '점 x_5x_2\large x_7을 잇는 선분 위에 있고''점 x_5x_2\large x_4을 잇는 선분 위에 있고'로 수정합니다.

 

※알립니다!

문제1이 여백 패르마 친구에 의해 해결됐습니다!

댓글 36

  • 프로벤젠 2018.09.03 18:33:19

    폐포를 더 쉽게 정의해 주실 수 있으신가요?

    무슨 말인지 잘 모르겠어요...

    좋아요0 댓글수0
  • 시그마 2018.09.03 20:43:02

    문제 1은 수학적 귀납법으로 증명하면 어떨가요?

    좋아요0 댓글수1
    • 프로벤젠 2018.09.03 23:25:28

      차원이 n차원이라서 수학적 귀납법이 유일한 해결책일 것 같네요.

      좋아요0
  • 뉴턴의 사과 2018.09.03 21:19:56

    두 점을 포함하는 볼록 폐포는 결국 두 점을 잇는 선분 아닌가요?

    좋아요0 댓글수1
    • 아인수타인 2018.09.04 00:05:39

      그럴 것 같은데요.

      좋아요0
  • 김우현 기자 2018.09.04 00:06:16

    폐포에 대한 설명이 부족했지요? 풀이에 필요한 정도만 얘기하면, 뉴턴의 사과 친구 말대로 한 점의 볼록 폐포는 그 점, 두 점의 볼록 폐포는 두 점을 잇는 선분, 세 점의 볼록 폐포는 세 점이 만드는 삼각형이라고 생각하면 됩니다. 곧 출제자인 최수영 교수님과 상의해 엄밀하게 정의하도록 할게요!laugh

    좋아요1 댓글수3
    • 시그마 2018.09.04 11:58:03

      감사요~

       

      좋아요0
    • 프로벤젠 2018.09.04 17:08:20

      그러면 두번째 그림 예시는 빨간색 삼각형 볼록 폐포 안에 초록색 점인 볼록 폐포가 들어있기 때문에 라돈의 정리에 성립하는 것인가요? 

      좋아요0
    • 김우현 기자 2018.09.04 18:05:59

      맞습니다!

      좋아요0
  • 프로벤젠 2018.09.04 17:14:08

    문제2에 점 @은 세 점 x_4, x_6, x_7을 꼭짓점으로 하는 삼각형 내부에 있다.

    에서 @에 들어갈 점이 무슨 점인가요?

    아니면 제가 잘못 이해하고 있는 건가요?

    좋아요0 댓글수1
    • 김우현 기자 2018.09.04 18:05:02

      수식 하나가 표시가 안됐네요! @부분에 x_1이 들어가야 합니다. 잦은 오타 죄송해요crying 

      좋아요0
  • 모두다같이 2018.09.04 20:35:52

    문득 궁금해진 건데 교수님들은 이런 문제를 내실 생각을 어떻게 하신 걸까요ㅋ..

    좋아요0 댓글수0
  • 수학장 2018.09.04 21:56:27

    문제 1번은 일단 d차원에서 d+2개의 점 중 어떤 4개 이상의 점이 어떤 2차원 공간 안에 항상 있다는 걸 증명하면 되지 않을까요

    좋아요0 댓글수0
  • 여백 패르마 2018.09.09 19:49:58

    (1)번 풀이

    d차원 공간에 있는 d+2개의 점의 집합 \left \{ x_1, x_2,...x_{d+2} \right \}\subset \mathbb{R}^d을 고려하자. 

    Lemma (1)) \sum_{i=1}^{d+2}a_ix_i=0 , \sum_{i=1}^{d+2}a_i=0 ··· (1)를 만족하는 점의 계수(a_1, a_2,...,a_{d+2})는 언제나 존재한다. 

    pf(1)) 미지수(계수)는 d+2개이고, 위의 방정식은 각각의 점에 관한 방정식이고, 마지막 점의 계수는 a_1, a_2,.., a_{d+1}에 관한 식으로 나타낼 수 있게 때문에, 방정식은 d+1개이다. 미지수보다 방정식이 더 적기 때문에 그 방정식의 해가 존재함을 알 수 있다. (실질적으로 수많다.)

    <본 증명>

    (1)방정식의 풀이 a_1, a_2,...,a_{d+2}를 고정시키자. 이때 a_i중 양수인 계수의 집합을 X라고 하자. 그리고, 음수인 계수의 집합을 Y라고 하자. 

    그러면 X, Yp를 공통으로 함으로 두개의 볼록 페포는 교차함을 알 수 있다. 

    p=\sum_{i\in X}\frac{a_i}{A}x_i=\sum_{j\in Y}\frac{-a_j}{A}x_j(A=\sum_{i\in X}a_i=-\sum_{j\in Y}a_j)

    Lemma (2)) p는 X의 점의 볼록 조합이고, Y의 점의 볼록 조합이다. 

    pf (2)) \sum_{i\in X}\frac{a_i}{A}=1이고, \sum_{j\in Y}\frac{-a_j}{A}=1이므로, p는 X의 점의 볼록 조합이고, Y의 점의 볼록 조합이다. 

    <본 증명>

    모든 볼록 조합의 집합과 주어진 점의 볼록페포와 같음으로, 볼록 폐포가 교차하는 두 부분 집합 X, Y으로 분할할 수 있음을 알 수 있다. 

    Q.E.D

     

    좋아요1 댓글수10
    • 여백 패르마 2018.09.09 19:50:31

      1번 풀이입니다. 

      좋아요0
    • 김우현 기자 2018.09.10 17:13:04

      주정훈 멘토가 '잘 푼 거 같다'는 의견을 전했어요! lemma1 증명에 약간의 비약이 있으나 크게 상관은 없다고 합니다. 출제자인 최수영 교수님께서 최종 확인하면 1번 문제 해결이네요! 

      좋아요0
    • 뇌요미 2018.09.11 22:40:19

      그런데 왜 Lemma (2)) p는 X의 점의 볼록 조합이고, Y의 점의 볼록 조합 인거죠???????

      좋아요0
    • 뇌요미 2018.09.11 22:40:19

      그런데 왜 Lemma (2)) p는 X의 점의 볼록 조합이고, Y의 점의 볼록 조합 인거죠???????

      좋아요0
    • 뇌요미 2018.09.11 22:40:19

      그런데 왜 Lemma (2)) p는 X의 점의 볼록 조합이고, Y의 점의 볼록 조합 인거죠???????

      좋아요0
    • 여백 패르마 2018.09.12 07:43:21

      pf(2)에 써져있습니다. 그리고 왜 같은 댓글이 3개이지?

      좋아요0
    • 모두다같이 2018.09.12 18:53:23

      여백페르마님  Lemma1에 시그마가 있는 두 식중, 계수가 있는 첫번째 등식에서 x들은 '(a_1, ... , a_d)처럼 d차원인 여러 좌표들'로 보면 되나요?

      그리고 Lemma1의 pf1))중에 마지막 점의 계수를 a_1, a_2, ... , a_d+1에 관한 식으로 나타낼 수 있는 이유도 궁금해요.

      혹시 d차원 도형을 나타내는데 필요한 꼭짓점의 최소 개수가 d+1개 라서인가요?

      풀이를 꼭 완전히 이해해 보고 싶습니다!

      좋아요0
    • 뉴턴의 사과 2018.09.12 20:55:21

      저는 위상적 스타일로 해보겠습니다

      좋아요0
    • 여백 패르마 2018.09.13 07:49:26

      마지막 계수는 1-(a_1+a_2+...+a_{d+1})입니다. 

      그리고, x는 좌표가 아닙니다. 볼록조합의 식을 변형하면 점-점형식 백터의 의 합이 됩니다.

      좋아요0
    • 김우현 기자 2018.09.14 14:48:09

      출제자 확인 결과, 정답으로 확인됐습니다. 축하드려요, 여백 패르마 친구!

      이번 문제는 '부분해결' 없이 소문제 2번까지 풀리면 '해결' 딱지를 붙이겠습니다!

      좋아요0
  • Simon 2018.09.12 19:31:25

    오랜만입니다

    좋아요0 댓글수1
    • 프로벤젠 2018.09.13 16:36:56

      저도ABCD의 교집합이 BD의 교집합과 같다는 과정에서는

      그림을 통해 확인가능하다고 생각합니다.

      그리고 제가 생각하기에는 BD의 교집합을 입체적인 관점에서 보았을 때는 직선이상의 차원에서 겹칠 수 있다고 생각합니다

      그러니 라돈의 정리를 BD교집합이 사면체임을 확인하는데 사용해야 문제가 풀릴 듯 싶습니다..

      좋아요0
  • 모두다같이 2018.09.12 23:15:57

    문제2번을 푸는 데 라돈의 정리가 어떻게 쓰이는 지 궁금해요..

    좋아요0 댓글수3
    • Simon 2018.09.13 08:34:06

      그건 잘 모르겠는데 확실한 건 문제에 오타가 있는것 같네요. 위에 풀이를 봐 주세요.

      좋아요0
    • 프로벤젠 2018.09.13 21:44:12

      저도 simon님 말씀처럼 문제가 있는 것 같긴 하네요.

      문제를 푸는데에는 오류가 없지만 A와 C 라는 사면체가 있는 이유를 잘 모르겠네요.

       

      아니면 저희가 생각하는 그림과 다른 경우가 있는 것 아닐까요?

      좋아요0
    • 김우현 기자 2018.09.13 21:51:42

      이런! 주정훈 멘토와 상의한 결과 문제에 오류가 있는 것 같다고 해요. 글자엔 오타가 없으니 내용을 다시 한번 검토하겠습니다. 잠시만 기다려주세요!crying

      좋아요0
  • 김우현 기자 2018.09.14 14:37:24

    검토 결과 오류가 발견돼 문제2 중 일부(x_5x_2와 x_7를 잇는 선분 위에 있고→x_5x_2와 x_4를 잇는 선분 위에 있고)를 수정했습니다. 혼란을 드려 죄송합니다.

    더욱 꼼꼼히 검토하도록 하겠습니다!crying

    좋아요0 댓글수0
  • Simon 2018.09.15 17:19:19

    수돌이님이 풀기 전에 빨리 풀어야겠다는 생각에 열심히 풀어봤습니다.

    좋아요0 댓글수4
    • 여백 패르마 2018.09.16 21:37:07

      출제자님 이 풀이 학인해주시길 바랍니다. 

      좋아요0
    • 김우현 기자 2018.09.17 00:15:55

      빨라요! 주정훈 멘토가 검토 중이니 잠시 기다려주세요!laugh

      좋아요0
    • 김우현 기자 2018.09.20 10:15:48

      현재 출제자 검토 중입니다~angel

      좋아요0
    • 여백 패르마 2018.09.23 18:34:15

      빨리 검토해주세용~

      좋아요0