본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[슬기로운 수학생활] 슬10. 속이 빈 단색 삼각형
수학동아 2021.01.29 17:40

 

 

평면에 2n개의 점이 임의의 세 점이 한 직선 위에 있지 않도록 배치되어 있다 (n은 100 이상이다). n개의 점은 빨간색, n개의 점은 파란색으로 색칠되어 있다. 2n개 점들 중 세개의 같은 색 점을 꼭지점으로 하고, 내부에 다른 점들이 없는 삼각형을 속이 빈 단색 삼각형이라고 하자.

 

(1) 어떤 상수 c_{1}> 0이 있어서, 어떤 점 배치에 대해서도 속이 빈 단색 삼각형의 개수가 항상 c_{1}n 이상임을 보여라.

(2) 어떤 상수 c_{2}> 0과 \alpha > 1이 있어서, 어떤 점 배치에 대해서도 속이 빈 단색 삼각형의 개수가 항상 c_{2}n^{\alpha } 이상임을 보여라.

(3) 어떤 상수 c_{3}> 0이 있어, 어떤 점 배치에 대해서도 속이 빈 단색 삼각형의 개수가 항상 c_{3}n^{2} 이상임을 증명할 수 있을까?

  •  
    빅수비 Lv.11 2021.01.29 20:09

    1번은 c1이 충분히 작다면 c1n도 충분히 작아질 수 있기때문에 c1n이 양수임을 보이기만 하면 된다는 건가요?

    그런데, 그게 맞다면 다른 문제들도 양수임을 보이기만 한다면 될텐데 그건 아닌거 같아서요.....

    문제 이해를 잘 했는지 모르겠습니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      출제자(슬기) Lv.2 2021.01.29 21:37

      문제에서 말하는 상수들은 n에 관계 없는 상수들입니다. 모든 n에 대해 주어진 조건을 만족하는 어떤 고정된 상수가 있는지가 질문입니다.

      좋아요0
  •  
    Q Lv.2 2021.01.31 17:02
    확인요청중

    (1)

    최하단의 가장 왼쪽에 있는 점을 O라고 합시다.

    일반성을 잃지 않고 O가 파란색 점이라고 할 수 있습니다.

    나머지 모든 파란점들을 O를 기준으로 각도 정렬합시다.

    그러면 파란 점들을 가장 반시계 방향에 있는 점부터 P_1, P_2, ..., P_{n-1} 이라고 할 수 있습니다.

    임의의 연속한 네 점 P_k, P_{k+1}, P_{k+2}, P_{k+3} 을 생각해 봅시다.

    영역 \angle P_kOP_{k+3}  내부에 있는 점들(파란점은 P_k, P_{k+1}, P_{k+2}, P_{k+3} 밖에 없고 빨간점들이 몇 개 있을 것이다)

    만 생각했을 때 적어도 한개의 속 빈 단색 삼각형이 존재한다는 것을 증명합시다.

    그러면 적어도 \lfloor (n-1)/3 \rfloor 개의 속 빈 단색 삼각형이 존재하므로 (1)번의 명제를 증명할 수 있게 됩니다.

     

    i) OP_k, P_{k+1}, P_{k+2}, P_{k+3} 가 볼록 오각형을 이룰 경우

    귀류법을 사용하기 위해, 이 영역에 있는 점들만 사용하여 속 빈 단색 삼각형을 만들수 없다고 가정합시다.

    그러면, \Delta P_kOP_{k+1}, \Delta P_{k+1}OP_{k+2}, \Delta P_{k+2}OP_{k+3} 내부에 빨간 점들이 적어도 하나씩 있어야 하고, 그렇게 되면 빨간점들끼리 이루는 삼각형이 속 빈 단색 삼각형이므로 가정에 모순이 되어, 이 영역에 있는 점들만으로 적어도 하나의 속빈 단색 삼각형을 만들 수 있습니다.

     

    II) OP_k, P_{k+1}, P_{k+2}, P_{k+3} 가 볼록 사각형을 이룰 경우

     

    일반성을 잃지 않고 위와 같은 형태라고 합시다.

    위와 같은 가정으로 귀류법을 사용하면,

    \Delta P_kOP_{k+1}, \Delta P_{k+1}OP_{k+2}, \Delta P_{k+2}OP_{k+3}, \Delta P_{k+1}P_{k+2}P_{k+3} 내부에 점이 적어도 하나씩 존재해야 하므로 총 네개의 빨간점이 존재합니다.

    한편, 적절한 네개의 빨간점을 사용하면 적어도 2개의 disjoint 하고 속에 빨간점이 없는 단색 삼각형을 얻을 수 있는데, 이 단색 삼각형들 내부에 있을 수 있는 점은 P_{k+2} 뿐이므로 적어도 두 단색 삼각형 중 하나는 속 빈 단색 삼각형입니다. 따라서 가정에 모순입니다.

     

    iii) OP_k, P_{k+1}, P_{k+2}, P_{k+3} 가 볼록 삼각형을 이룰 경우

    위와 마찬가지의 방법으로 증명하면 되는데, 적어도 5개의 빨간 점이 필요하고 적절한 5개의 빨간점을 사용하면 disjoint 한 3개의 속에 빨간점이 없는 삼각형을 얻을 수 있는데, 이들 내부에 들어갈 수 있는 점들은 P_{k+1}, P_{k+2} 뿐이므로 적어도 하나의 빨간 속 빈 단색 삼각형이 존재합니다. 따라서 가정에 모순.

    댓글 작성하기 좋아요0 댓글수2
    •  
      파스칼 Lv.7 2021.01.31 22:22

      (그다지 의미는 없지만)ii와 iii에서 볼록 삼각형과 볼록 사각형에 대한 이야기가 나오는데 점이 다섯 개 표시되어있네요

      제 생각에는 iii번 열각 PkPk+1Pk+1가 O의 반대쪽, 열각 Pk+1Pk+2Pk+3도 O의 반대쪽일 때를 의미하는 듯한데요

      그 부분이나 대칭에 관한 내용이 약간 생략되었지만 그리 중요한 부분은 아니기에 이걸로 1번은 해결할 수 있을 듯하네요

      발상이 대단합니다!! 이 방법을 응용하면 2,3번에서도 답을 찾을 수 있을 것 같아요

      (수정) ii와 iii은 다섯개의 점이 이루는 다각형이 볼록사각형이나 볼록삼각형임이 아니라 몇개의 점이 볼록사각형 또는 볼록삼각형 내부로 들어가 전체가 볼록사각형 또는 볼록삼각형을 이룬다는 말이었네요

      좋아요0
    •  
      최기자 Lv.4 2021.02.07 16:48

      김다인 멘토가 검토한 결과 1번을 잘 풀어준 것 같다고 하네요!^^

       

      수고했어요~! 다음 문제에도 함께 도전해 봐요!^^

      좋아요0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911