본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[슬기로운 수학생활] 슬8. 볼록다각형을 세보자!
수학동아 2020.12.03 11:25

평면에 n개의 점들의 집합 S가 있어 어떤 두 점도 겹치지 않고, 어떤 세 점도 한 직선 위에 놓여 있지 않다.

 

 

 

모든 k\geq 3에 대해 S의 k개 점들을 꼭짓점으로 가지고 내부에 S의 다른 점이 없는 볼록다각형의 개수를 f_k라고 하자. 편의상 f_0=1, f_1=n, f_2=\frac{n(n-1)}{2}로 두자.

 

 

 

문제1 f_0- f_1+ f_2-f_3+f_4-\cdots의 값은 얼마인가?

 

 

 

문제2 f_1- 2f_2+ 3f_3-4f_4+\cdots의 값은 얼마인가?

  •  
    다시 도전
    M.Poseidon Lv.6 2020.12.04 11:00 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수4
    •  
      Sin X Lv.5 2020.12.04 12:54

      각각 몇번에 관한 것인가요?

      저는 1번은 0 임을 증명한것 같습니다.

      좋아요0
    •  
      M.Poseidon Lv.6 2020.12.04 12:57

      첫 번째는 1번입니다. 두번째는 2번입니다

      좋아요0
    •  
      출제자(슬기) Lv.2 2020.12.06 15:15 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      최기자 Lv.4 2020.12.24 08:26

      김다인 멘토의 풀이 검토입니다.^^

       

      (1,2번) 문제를 잘못 이해하신 것 같습니다. 다시 한번 문제를 차근차근 읽어보고, 이해가 되지 않는 점은 질문해주세요!

      좋아요0
  •  
    M.Poseidon Lv.6 2020.12.04 11:32 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      Sin X Lv.5 2020.12.06 14:27

      저는 2번을 몇개 시뮬레이팅 한 결과 내부의 점수로 답이 나온듯 한데 혹시 2번 답 뭘로 구하셨나요?

      좋아요0
  •  
    무한대의끝을본남자 Lv.7 2020.12.05 14:49

    제가 접근하기에 이것은 점화식과 비슷한 형태로 표현이 가능할것같습니다

    점화식이아니어도 어느 함수f를 정의하여

    망원급수형태로 접근가능할듯합니다

     

    k-1경우에서 오목 다각형을 빼면 S의 점이 들어있는 다각형이나오는데

    그점들을 한번더 연결하면 k-1이상의 오목 다각형이 나옵니다

     

    이를 이용하여 1번을 접근할수있지않을까합니다

    댓글 작성하기 좋아요0 댓글수0
  •  
    Sin X Lv.5 2020.12.06 14:26 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수3
    •  
      Sin X Lv.5 2020.12.06 14:27

      1번이 0 임을 증명한것입니다.

      2번은 볼록다각형 안의 점 수가 답일것으로 예측됩니다.

      좋아요1
    •  
      M.Poseidon Lv.6 2020.12.06 16:49

      풀이 올렸습니다

      좋아요0
    •  
      최기자 Lv.4 2020.12.24 08:25

      김다인 멘토의 풀이 검토입니다.^^

       

      잘 풀었습니다! 다만 풀이 중 넣은 다이어그램은 무엇을 계산한 것인지 파악하기가 어렵고, 풀이 중에도 그 의미가 명확하게 나타나있지 않습니다. 말이 조금 길어지더라도 본인의 아이디어를 글로 풀어서 서술하는 방법을 연습해보세요! \sum (-1)^I nCi를 계산해야되는데 (-1)^i이 빠진 오타가 두 부분 보이네요!

      좋아요0
  •  
    M.Poseidon Lv.6 2020.12.06 16:30

    k개의 점을 꼭짓점으로 가지는 볼록다각형의 개수 fk는 n개 중에서 k개의 점을 선택하는 것 이므로 fk=nCk 정의 할 수 있습니다.

    점이 n개 이므로 n각형이 최대이다.

    f0=1=nC0 , f1=n=nC1 로 치환할 수 있다.

    f0-f1+f2-f3+f4-......= nC0-nC1+nC2-nC3+nC4-......+(-1)n * nC바꿀 수 있다.

    이항 정리에 의해 (X+Y)n=nC0*Xn+nC1*Xn-1Y+nC2*Xn-2Y2+.......+nCn-1XYn-1+nCnYn 이 성립한다.

    위에 식에 X=1, Y=-1 을 대입하면 0= nC0-nC1+nC2-nC3+nC4-......+(-1)n * nCn 되므로 

    f0-f1+f2-f3+f4-......= nC0-nC1+nC2-nC3+nC4-......+(-1)n * nC=0

    문제 1번의 답은 0 입니다.

    Lemma nCr=(n/r)n-1Cr-1

    증명 nCr=n!/(r!(n-r)!)   ,  (n/r)n-1Cr-1=(n/r)*(n-1)!/((r-1)!(n-r)!)=n!/(r!(n-r)!) 따라서 위에 식은 성립한다.

    f1-2f2+3f3-4f4+.......=nC1-2nC2+3nC3-4nC4+......+(-1)n-1 * nC바꿀 수 있다.

    nC1-2nC2+3nC3-4nC4+......+(-1)n-1 * nCn는 Lemma에 의해 n*n-1C0-2*n/2*n-1C1+3*n/3*n-1C2-.......+(-1)n*n/n*n-1Cn-1 로 바꿀 수 있습니다.

    n*n-1C0-2*n/2*n-1C1+3*n/3*n-1C2-.......+(-1)n*n/n*n-1Cn-1=n{n-1C0-n-1C1+n-1C2-n-1C3+......+(-1)nn-1Cn-1}

    문제 1번에서 f0-f1+f2-f3+f4-......= nC0-nC1+nC2-nC3+nC4-......+(-1)n * nC에서 n에 n-1을 대입하면 n-1C0-n-1C1+n-1C2-n-1C3+......+(-1)nn-1Cn-1=0 이라는 식을 얻을 수 있습니다.

    그러므로 f1-2f2+3f3-4f4+.......=nC1-2nC2+3nC3-4nC4+......+(-1)n-1 * nCn=n*0=0 입니다.

    따라서 문제 2번의 답은 0 입니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      Sin X Lv.5 2020.12.06 17:13

      죄송한데;; 문제를 잘못 이해하신것 같습니다.

      문제에서 f_k는 단순히 k개의 점을 뽑는 가짓수가 아닌, 내부의 아무 점도 존재하지 않는 볼록 k각형의 개수입니다.

      1번과 2번 모두 다시 푸셔야 할것 같습니다.

      좋아요0
  •  
    Sin X Lv.5 2020.12.06 17:16

    댓글 작성하기 좋아요4 댓글수2
    •  
      Sin X Lv.5 2020.12.06 17:24

      내부에 점이 있는경우 상쇄할수 있다는 아이디어를 이용하여 풀었습니다.

      좋아요0
    •  
      무한대의끝을본남자 Lv.7 2020.12.06 17:39

      저도 sin님과 비슷한 아이디어로 접근했지만

      오류가있어 수정중입니다

       

      풀이 나중에 올릴게요

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

  • ☎문의 02-6749-3911