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

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국16. 모자와 컵과 도형

2018.03.30

같이 풀어볼까?

네이버밴드 구글플러스

 

 

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

 

 

평면 위의 점들을 생각하자. 만약 점 a개를 x좌표의 크기 순서대로 쭉 이었을 때 오목한 형태를 이룬다면 점들이 a-cap을 이룬다고 한다. 마찬가지로, 점 b개를 x좌표의 크기 순서대로 쭉 이었을 때 볼록한 형태를 이룬다면 점들이 b-cup을 이룬다고 한다. 마지막으로, 점 n개(n≥3)가 어떤 볼록다각형의 꼭짓점을 이룬다면 점들이 n-gon을 이룬다고 한다.

 

왼쪽부터 각각 4-cap, 5-cup, 6-gon.

 

 


[문제]

 

임의의 세 점이 한 직선위에 있지 않고 임의의 두 점이 같은 x좌표를 가지지 않는 N개의 점이 있다고 하자.

 

 

문제1.

만약 이 N개의 점들 안에 a-cap과 b-cup이 없다면, N\leq \begin{pmatrix} a+b-4\\a-2 \end{pmatrix}임을 보여라. 여기서 N\geq a, b\geq 2다.

 

 

 

문제2.

만약 점 N개의 점들 안에 4-cap과 n-gon이 없다면 N\leq \binom{n}{2}-n+2일까? 여기서 N\geq n\geq 2다.

 

 

 

 

*\binom{n}{m}은 이항계수로, n개의 물건 중 m개를 고르는 경우의 가지 수다. nCm이라는 표기법으로도 나타낸다.

 

 

댓글 35

  • onecube 2018.03.30 23:30:33

    그냥 궁금해서 묻는건데 n이 어떤 자연수던간에 항상 n-gon이 없으려면 N개의 점을 각각 이은 기울기가 다 같아야 (N개의 점이 모두 한 직선상에 있어야) 되는거 맞나요?

    좋아요0 댓글수2
    • 누군가 2018.03.31 12:54:24

      꼭 그럴 필요는 없습니다. 간단한 경우만 생각해보면 n=4 일때 그림처럼 N-1개의 점이 한직선에 있고 1개 만 그 직선에서 벗어나 있다고 생각해봅시다. 

      4-gon을 만들기 위해 점 4개를 선택한다고 하면 두가지경우 중 하나입니다.

      1.한 직선상의 4개의 점 2.한 직선상의 3개의 점과 그 직선위에 없는 점 1개.

      어떤 경우라도 만들어진 도형의 변 위에 있는 점이 있으므로(볼록다각형의 꼭짓점을 이루지 않으므로) 4-gon을 이룰 수 없습니다.

      좋아요0
    • 깜냥 2018.04.01 23:02:53

      /resources/comment/2018/04/2bf876ffddb5a9c418870974538b1257.png

      문제에서 볼록다각형을 이루어야 한다고 했기 때문에

      위 그림처럼 n개의 꼭짓점을 이었을 때 오목다각형이 되면 n-gon이 없습니다.

       

       

      좋아요0
  • muse 2018.04.01 10:24:11

    a-cap이나 a-cup이 있으면 무조건 a-gon이 있겠군요.

    좋아요0 댓글수6
    • 김우현 기자 2018.04.08 10:56:46

      Simon 친구, 친구들이 이해하기 쉽게 반례를 하나 들어주실 수 있으신지요~ +0+

      좋아요0
    • Simon 2018.04.08 14:15:27

      위 도형은 4-cup이지만 4-gon은 아니라는 것을 알 수 있습니다.

      또한, 이 도형을 x-axis에 대해 대칭시키명 4-cap이지만 4-gon이 아닌 도형을 만들 수 있습니다.

      (a-cup or a-cap)이 아닌 (a-cup and a-cap)인 경우에 대하여는 추가 연구가 필요하겠습니다.

      그보다 밑에 제 증명은 맞는 증명인가요? 친구랑 내기를 하여 가슴을 졸이고 있답니다....

      좋아요0
    • 구머 2018.04.08 14:18:51

      저는 저 도형이 4cup이라고 생각하지 않는데, 그 이유가 abc가 3cap이기 때문입니다.

      좋아요0
    • Simon 2018.04.08 14:35:20

      3-cap이 존재한다고 4-cup이 아니라고는 할 수 없지 않나요?

      좋아요0
    • 구머 2018.04.08 14:40:20

      일단 이 문제에서는 아래로 볼록, 즉 cup의 정의가 '기울기가 순서대로 증가'이라고 되있습니다(아래 댓글 참고). 그런데 abc가 3cap이므로, 기울기가 감소하는 구간이 존재하고, 따라서 4cup이라고 할수 없습니다.

      좋아요0
    • Simon 2018.04.08 15:37:25

      아 제가 잘못 생각한 것 같군요.

      하지만 제 증명을 다시 검토해 본 결과 특별히 달라지진 않는 것 같습니다 감사합니다~

      좋아요0
  • 수학장 2018.04.01 13:53:27

    예시의 4-cap이 왜 오목한 거죠? 오목하다는 게 정확히 뭔가요?

    좋아요0 댓글수2
    • muse 2018.04.01 14:52:38

      제가 보기에는 아마 저게 아래로 튀어 나와 있으면 오목, 위로 튀어 나와 있으면 볼록이라는 것 같습니다.

      좋아요0
    • 김우현 기자 2018.04.02 08:49:13

      muse 친구 말대로, 점을 이었을 때 동굴같은 모양이면 오목, 컵 모양이면 볼록하다고 합니다!cool

      좋아요0
  • 권순용 2018.04.01 15:32:58

    A(1, 1), B(2, 3), C(3, 3), D(4, 1)이라 할 때 A,B,C,D는 4-cap인가요?

    좋아요0 댓글수1
    • 지나가던 사람 2018.04.01 21:26:20

      4-cap이 맞습니다.

      왜냐하면

      x값의 순서대로 정렬했을때 a와b를 있는 선분이 위로 올라가서 최댓값을 찍고 선분c,d로 내려왔기 때문인데,

      제 생각에는 x값이 가장 낮은점과 x값이 가장 큰 점(a와d)을 있는 선을 그리고 최댓값이 그선 위에 있다면(최댓값의x좌표에 해당하는 선분a,d의좌표를 점 e라하고

      e의 y좌표와 최댓값의 y좌표를 비교해 보면 위에 있는지 아래에 있는지 알수 있죠.)a-cap인 것 같습니다.(b-cup도 마찬가지로,반대로 생각하면 됩니다.)

      여기선 ad가  y=1이 되는 군요.최댓값이 3이니 4-cap이 맞습니다!

      그림1 그림2 그림3

      좋아요0
  • c언어 2018.04.03 01:44:46

    n이 어떤값 이하라는 거는 한계가 있다는 소린데, 아래의 모양이면 n이 무한히 커져도 되지 않나요?

    좋아요0 댓글수1
    • 수학장 2018.04.03 08:08:12

      1,2,4,5번째 점을 이으면 4-cap이 되는군요

      좋아요0
  • muse 2018.04.03 10:41:16

    우선 (1)번 문제를 관찰해 봅시다.

    어떤 점 N개로 이루어진 모양에 a-cap, b-cup이 없을 때 N의 최댓값을 f(a, b)라고 합시다.

     

    여기 보니까 a, b의 최솟값은 2네요. 2-cap, 2-cup은 그냥 직선이니까 이 두 가지 모양이 없으려면 그냥 점이 하나밖에 없어야 합니다. 따라서 f(2, 2)=1.

    마찬가지로 f(2, i)나 f(i, 2)도 1입니다. 직선이 생기면 안 되기 때문입니다.

     

    f(3, 3)은 얼마일까요? 3-cap, 3-cup이 없어야 합니다.

    여기서 문제가 살짝 에매해 지는데, cap과 cup의 정의를 이런 경우도 허용한다고 봐야 할지요.

    만약 이것을 허용하면, f(3, 3)은 2가 됩니다. 세 점을 놓으면 어떻게든 3-cup 또는 3-cap이 만들어지거든요.

     

    파스칼의 삼각형이 떠오르긴 하지만, 그건 아닐 것으로 보입니다.

    좋아요0 댓글수1
    • 김우현 기자 2018.04.03 16:42:27

      네, 위 그림도 각각 cap과 cup입니다. 백진언 연구원 님에 따르면, 선분의 기울기가 순서대로 낮아지거나 높아지면 된다고 해요!

      좋아요0
  • 지나가던 사람 2018.04.03 23:22:53

    다섯 개의 점을 평면 위에 놓았을 때 ,반드시 볼록사각형이 만들어 진다고 하는데 어떻게 증명하는 것인가요?

    좋아요0 댓글수3
    • muse 2018.04.04 08:00:58

      수학동아 에르되시 코너에서 나왔던 것으로 기억합니다.

      좋아요1
    • 지나가던 사람 2018.04.05 18:26:13

      방금 찾아봤는데 '해피앤딩 문제'라고 나오더군요!

      감사합니다!

      (에르되시 팔 5화)

      좋아요1
    • 김우현 기자 2018.04.08 10:51:43

      수학동아 광팬 인증!!laugh

      좋아요0
  • Simon 2018.04.05 22:42:33

    증명 완료하였습니다

     

    좋아요0 댓글수9
    • Simon 2018.04.05 23:10:02

      질문하실 부분이나 개선하실 부분 있으시다면 얘기해 주시기 바랍니다.

      좋아요0
    • 수학장 2018.04.05 23:14:28

      ??? 갑분싸

      좋아요0
    • 구머 2018.04.08 15:18:21

      두번째 페이지의 뒷부분의 계산식을 더 자세하게 설명해주실수 있으신가요? 그리고 Lemma1이 어떻게 사용된건지 설명 부탁드립니다 

      좋아요0
    • Simon 2018.04.08 15:36:35

      다른 질문은 없으신지요?

      좋아요0
    • 구머 2018.04.08 16:21:39

      2페이지 첫부분 반례: 그림에서 4 cap은 존재하나 4cup이 없습니다.ㆍ

      좋아요0
    • 구머 2018.04.08 16:25:15

      그리고 lemma 2의 증명에서 윗부분에 논쟁이 된 부분 때문에 문제가 생기네요.

      좋아요0
    • Simon 2018.04.08 18:44:46

      오류를 찾아 주셔서 감사합니다 빠른 시일 내에 보완하도록 하겠습니다

      (잘가렴 내 문상아~

      좋아요0
    • 구머 2018.04.08 18:49:17

      ㅎㅎ네 그래도 아이디어는 되게 좋았어요.

      좋아요0
    • 김우현 기자 2018.04.09 10:01:32

      Simon 친구의 풀이에 대한 백진언 연구원 님의 의견입니다!

       

      ① Lemma3은 '\small N\geq 7일 때, 4-cap 또는 4-cup이 존재한다'고 바꾸는 게 좋을 것 같아요.

      예를 들어 모든 점이 하나의 cup을 이루는 경우 4-cap이 존재하지 않을 수도 있거든요.

       

      ②따라서 문제 1번의 (iii)\small min(a, b)\geq 4에서 \small N> \binom{2a-4}{a-2}일 때 보일 수 있는 사실은 'a-cup' 또는 'a-cap'의 존재성입니다. 

      귀납법 가정(Lemma3, 4-cap 또는 4-cup이 존재한다)이 틀렸기 때문에 (iii)\small min(a, b)\geq 4의 풀이 중 (ii)에서 귀납법을 적용할 수 없습니다.

       

      ③마찬가지로 문제 (ii)번의 (iv)에서도 \small N이 7 이상이라고 해서 반드시 4-cap이 존재하는 건 아닙니다.

      좋아요0
  • 0gzg♡ 2018.07.10 18:20:57

    그런데 cap, cup, gon이 오목하게 들어간 모양은 안되는 건가요?

    좋아요0 댓글수1
    • 김우현 기자 2018.08.17 13:38:46

      '오목하게 들어간 모양'이 정확히 무얼 뜻하는지 알려주세요~~.angel

      좋아요0