본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대37. 끝없는 정삼각형
수학동아 2020.01.02

평면 위에 n개의 점을 찍고 이 n개의 점을 꼭지점으로 가지는 정삼각형을 그립니다. 이때 n은 3과 같거나 큽니다(n\geq 3). 이렇게 해서 만들 수 있는 정삼각형의 수의 최댓값을 T(n)이라 합니다.

 

1. T(n)\leq \frac{n^2}{3}임을 증명하세요.

 

 

2. T(n)\geq cn^2이 항상 성립하게 되는 양수 c가 존재함을 보이세요.

 

위의 두 부등식을 통해 n이 매울 클 때 T(n)의 크기가 n^2 정도임을 알 수 있습니다. 아직까지 \lim_{n    o \infty }\frac{T(n)}{n^2}이 존재하는지 여부는 알려져 있지 않습니다. 이 값이 존재한다고 가정하고 다음을 증명하세요.

 

3. \lim_{n    o \infty }\frac{T(n)}{n^2}\leq 0.25

 

4. \lim_{n    o \infty }\frac{T(n)}{n^2}\geq 0.19

 

본 문제는 1, 2번은 리프 학생이, 3, 4번은 cube120 학생이 해결한 것으로 확인됐습니다.

모두 함께 힘을 모아줘서 고맙습니다. 수고했어요!

  •  
    리프 Lv.6 2020.01.02 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수4
    •  
      리프 Lv.6 2020.01.02

      1번 풀이입니다.

      사실 2개의 풀이를 생각했는데 동일한 결과가 나오길래 그냥 1개만 올렸습니다.

      좋아요0
    •  
      리프 Lv.6 2020.01.03

      1번은 다른 문제에 비해 쉬운 편이라 주말에 공개댓글로 다시 올리겠습니다.

      좋아요0
    •  
      수학동아 2020.01.13

      1번 문제를 해결했습니다. 축하합니다.^^ 2번 문제도 풀이를 달아 주세요. 구머 학생이랑 같이 얘기한 부분이 맞다고 하네요!

      좋아요0
    •  
      리프 Lv.6 2020.01.14

      2번 풀이도 올리려고 했는데 시간이 없어서 미루다 보니 cube120님이 먼저 올리셨네요. 저랑 구머님이 생각한 풀이가 아마도 cube120님의 풀이랑 같은 것 같습니다.

      좋아요0
  •  
    .... Lv.4 2020.01.02 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    .... Lv.4 2020.01.02

    2번의 의미가 n이 뭐든간에 부등식을 성립하게 하는 c가 존재한다는 것인가요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      리프 Lv.6 2020.01.02

      임의의 n에 대해 성립하는 어떤 상수 c가 존재해야 합니다.

      좋아요0
  •  
    .... Lv.4 2020.01.02

    C로 접근해야 할까요?

    댓글 작성하기 좋아요0 댓글수0
  •  
    sicma Lv.10 2020.01.02

    리프님 혹시 점 7개일때 찾은 최대 갯수가 몇개 나왔나요?

    댓글 작성하기 좋아요0 댓글수5
    •  
      리프 Lv.6 2020.01.03

      저는 1번 풀 때 T(n)을 직접 구하지 않아서 잘 모르겠네요... 일일이 계산하는 것도 문제를 파악하는 좋은 방법이지만 1번은 그냥 점 n개에 대해서 최댓값을 적당히 잡으면(?) 풀립니다. (점 n개에 대해서 정삼각형은 아무리 많아도 (n^2)/3을 넘을 수 없다는 것을 보이면 됩니다.)

      표현이 좀 애매해서 도움이 될 지는 잘 모르겠네요

      좋아요0
    •  
      mathwizard Lv.7 2020.01.10

      24개 아닌가요? 전 그렇게 나왔는데.

      좋아요0
    •  
      리프 Lv.6 2020.01.15

      24개가 나올 수 있나요? 1번에 따르면 T(7)은 기껏해야 16일텐데 그림 올려주시면 좋겠네요

      좋아요0
    •  
      mathwizard Lv.7 2020.01.15

      앗!죄송합니다, 제가 질문을 잘못 이해했어요. 근데, T(7)의 최대가 어떻게 해서 16이 될 수 있나요?

      좋아요0
    •  
      리프 Lv.6 2020.01.16

      1번 부등식에 대입하면 아무리 커도 T(7)은 16이하라고 나오는 것 같습니다

      좋아요0
  •  
    sicma Lv.10 2020.01.02

    그런데 1번을 증명하면 2번은 자동으로 되는 것이죠?

    댓글 작성하기 좋아요0 댓글수1
    •  
      리프 Lv.6 2020.01.03

      부등호 방향 반대에요.

      좋아요0
  •  
    구머 Lv.4 2020.01.03

    2번의 경우, 대학수학회 14번: 정육면체 분할해 정육면체 만들기 문제의 2번 문제 풀이를 이해하면 쉽게 풀 수 있습니당. 추가로 4번을 풀 때도 하한을 1/6까지 줄일 수 있게 됩니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      리프 Lv.6 2020.01.04

      그러네요. 점이 n(n+1)/2개 있을 때 정삼각형이 n(n+1)/2에 대한 이차식 나오기 때문에 c의 존재성이 바로 해결이 되네요. 진짜 볼 때마다 아이디어가 대단하신 것 같네요 ㄷㄷ

      좋아요0
  •  
    리프 Lv.6 2020.01.04

    1번 풀이입니다.

     

    어떤 선분을 한 변으로 갖는 정삼각형의 개수는 최대 2개임은 자명하다.

    정삼각형의 개수를 k개라 할 때,

    정삼각형의 모든 변을 세면 그 값은 3k가 될 것이고(동일한 선분이여도 다른 정삼각형의 변이면 다른 것으로 취급)

    선분에 대해 정삼각형의 변을 세면 선분은 n(n-1)/2개 인데 한 개의 선분은 최대 2개의 정삼각형의 변이 될 수 있으므로 변의 개수는 최대 n(n-1)개 일 것이다.

    따라서, k<(n^2)/3이고, 이는 k\leq T(n)을 만족하는 임의의 음이 아닌 정수에 대해 모두 성립하므로, T(n)<(n^2)/3이 성립한다.

     

    확인요청했던 풀이입니다.

    댓글 작성하기 좋아요2 댓글수10
    •  
      수학동아 2020.01.06

      안녕하세요!

      이 풀이는 멘토께 검토를 요청하도록 하겠습니다.^^

      좋아요0
    •  
      mathwizard Lv.7 2020.01.08

      '^'표시가 무엇인가요?

      좋아요0
    •  
      222 Lv.8 2020.01.08

      ^는 승이에요

      예를 들면 2^3은 2^{3}이어서 8이예요

      좋아요0
    •  
      최기자 Lv.4 2020.01.10 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      code Lv.4 2020.01.11

      2개의 풀이를 생각하셨다고 하셨는데, 혹시 다른풀이도 올려주실수있으신가요?

      좋아요0
    •  
      mathwizard Lv.7 2020.01.11

      '변의 개수는 최대 n(n+1)개 일 것이다.'가 무슨 뜻인지 알려주실 수 있나요?

      좋아요0
    •  
      리프 Lv.6 2020.01.12 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      리프 Lv.6 2020.01.12

      제가 말했던 2번째 풀이입니다.

       

      임의의 점 v_i를 원점으로 하는 극좌표계를 생각하자.

      이때, 원점이 아닌 점 (r,\theta )에 대해, (r,\theta+\frac{\pi}{3} )이 n개의 점에 포함되는 '점 (r,\theta )' 개수를 세주면 v_i를 포함하는 정삼각형의 개수가 될 것이다.

      즉, 임의의 점 v_i가 포함되어 있는 정삼각형의 개수는 최대 (n-1)개이므로, T(n)\leq \frac{n(n-1)}{3}임을 알 수 있다. (1차항이 있지만 마이너스여서 따로 문제될 것은 없고 극한 취하면 이차항만 남게 됩니다.)

      좋아요0
    •  
      리프 Lv.6 2020.01.12

      @mathwizard

      어떤 선분에 대해서 그 선분이 포함되는 정삼각형은 기껏해야 두 개 밖에 없습니다. (나머지 한 꼭짓점이 될 수 있는 곳이 위에 1개, 아래에 1개)

      따라서, 선분의 총 개수는 n(n-1)/2개 이므로, 정삼각형의 변의 개수는 아무리 많아도 n(n-1)개가 됩니다.

       

      한마디로 요약해서 변의 개수는 아무리 많아도 이 값을 넘지 못한다는 뜻입니다.

      좋아요0
    •  
      mathwizard Lv.7 2020.01.15

      설명 감사합니다^^

      좋아요0
  •  
    mathwizard Lv.7 2020.01.10

    T(n)을 구하는 방법이 무엇인가요? 직접 해보는 방법 말고는 없나요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      리프 Lv.6 2020.01.12

      문제는 T(n)의 값을 물어보는게 아니라 이 값의 최대 최소를 물어보고 있기 때문에 점들간의 관계에 대해 생각해보아야 합니다.

      직접 구하는 건 힘들 것 같네요.

      좋아요0
  •  
    부분해결
    cube120 Lv.5 2020.01.13

    2번 풀이입니다. 풀이에 앞서 점들의 집합 P에 대해 T(P)는 집합 P에서 만들어질 수 있는 정삼각형의 최대 개수를 말합니다. 

    proof)

    한 변의 길이가 m인 정삼각형을 그리고, 그 안에 격자점을 그린 집합 을 T_m이라 하자. 그림은 T_3를 보여주고있다.

    자명하게 |T_m|=(m+2)(m+1)/2 이다. 또한 T(T_m)=(m+4)(m+3)(m+2)(m+1)/24임도 계산을 통해 얻을 수 있다.

    임의의 자연수 n을 생각하자. 그리고 (m+2)(m+1)/2 <= n < (m+3)(m+2)/2 를 만족하는 자연수 m은 유일하다.

    이 때 정의에 의해 T(n) >= T(T_m) 임은 자명하고, 약간의 계산을 통해 T(n)/n^2 >= T(T_m)/n^2 > T(T_m)/{(m+3)(m+2)/2}^2 = 1/6 * m(m+1)/{(m+3)(m+2)}를 얻을 수 있다.

    m이 자연수이므로 m(m+1)/{(m+3)(m+2)}의 최솟값은 6/20이고, 따라서 다음을 얻는다. \frac{T(n)}{n^2}> \frac{1}{20} . 이제 c=1/20으로 잡으면 된다. 증명끝.

    댓글 작성하기 좋아요0 댓글수2
    •  
      cube120 Lv.5 2020.01.13

      참고로 T_m을 이용하면 \liminf_{n\rightarrow \infty}\frac{T(n)}{n^2} \geq \frac{1}{6} = 0.16667임을 얻을 수 있습니다. 문제 4번에 해당하는 하한을 얻기 위해서는 삼각형이 아니라 육각형 또는 원을 이용해야 할 것 같습니다.

      좋아요0
    •  
      김미래 기자 Lv.4 2020.04.02 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    구머 Lv.4 2020.01.14

    현 상황(4번)

     

    정육각형 배치의 경우, T(n)/n^2 의 값이 5/27이 된다는 결과를 얻었습니다. 이를 계산해보면 약 0.185...로, 반올림을 무시한다 할 때, 아주 아깝게 값이 모자랍니다. 하지만 정삼각형->정육각형->...등 변의 개수가 많을수록, 극한값이 조금식 커질 것 같다는 느낌이 듭니다. 지금은 과감하게 원형 배치에서의 T(n)/n^2 값을 계산하고 있고, 상당히 복잡하네요..

    댓글 작성하기 좋아요0 댓글수2
    •  
      cube120 Lv.5 2020.01.14

      그런가요? 저는 정육각형 정도만 되도 충분히 될꺼라 생각했는데,.. 다시 생각해봐야겠군요

      좋아요0
    •  
      구머 Lv.4 2020.01.14

      으아 카운팅에 오류가 있었어요ㅜㅜ 재검토한 결과 7/36이 맞는 것 같습니다. 풀이는 추후 작성하겠습니다! 아마 4번은 이걸로 해결이 될것 같고, 이제 3번만 풀면 될것 같군요.

      좋아요0
  •  
    해결
    cube120 Lv.5 2020.01.14

    4번입니다.

    proof)

    이번에는 한변의 길이가 m인 육각형 H_m을 생각하자.

    그러면 |H_m|=3m^2+3m+1 이고, T(H_m)=1/4*m(7m^3+14m^2+9m+2) 이다.

    따라서 T_m일때와 마찬가지로 정리하면 T(n)/n^2 >= 7/36 + O(n^(-1/2))를 얻는다. (여기서 O는 big-O 표기입니다.)

    따라서 \frac{T(n)}{n^2} \geq \frac{7}{36}=0.19444이다.

     

    댓글 작성하기 좋아요0 댓글수14
    •  
      수학동아 2020.01.14

      안녕하세요! 풀이 검토를 요청하려면 정답 확인 요청 버튼을 눌러 주세요~!^^

      좋아요0
    •  
      cube120 Lv.5 2020.01.14

      앗 마지막 줄에 실수로 lim을 안썼네요.  lim가 있다고 생각해주시면 감사하겠습니다!

      좋아요0
    •  
      리프 Lv.6 2020.01.15

      벌써 4번이 해결됐네요 ㄷㄷ 시간 나는대로 3번을 풀어보려고 하는데 제가 요즘 영재고 준비 때문에 너무 바빠서 따로 풀이를 올리지는 못할 것 같고 아이디어가 떠오르면 올려보도록 하겠습니다

      좋아요0
    •  
      cube120 Lv.5 2020.01.15

      오 리프님 영재고 어디 준비하세요?

      좋아요0
    •  
      리프 Lv.6 2020.01.16

      저는 일단 서울 준비하고 있습니다.

      좋아요0
    •  
      cube120 Lv.5 2020.01.16

      대전으로 오세요 밥 맛있어요 ㅋㅋ

      좋아요0
    •  
      리프 Lv.6 2020.01.16

      ㅋㅋㅋㅋ 지금 대전 다니시나요?

      좋아요0
    •  
      cube120 Lv.5 2020.01.16

      이번에 합격했습니다 ㅋㅋ 한살차이네요

      좋아요0
    •  
      리프 Lv.6 2020.01.16

      저랑 1살차이이신데 수학실력이 저보다 훨씬 뛰어나시네요 ㄷㄷㄷㄷ

      cube님 실력이면 서울 가고도 남을 것 같은데 혹시 대전을 선택하신 특별한 이유가 따로 있나요?

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.01.17

      저는 한국과학영재고등학교준비중이예요

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.01.17

      정삼각형은 예각삼각형에포함되니까

      조합론적으로 n에 3을선택하는경우의수-둔각삼각형-직각삼각형이되니까요

      좋아요0
    •  
      cube120 Lv.5 2020.01.18

      과학고는 수학 실력 뿐만 아니라 과학 실력도 중요하죠.

      저는 암기를 잘 못해서 생물과 지학 실력이 많이 부족했고, 실제로 입학시험에서도 생물과 지학은 거의 손도 못댔습니다.

      좋아요0
    •  
      최기자 Lv.4 2020.01.30 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      최기자 Lv.4 2020.03.31 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    리프 Lv.6 2020.01.16

    근데 부분해결 안 붙나요? 원래 소문제 해결하면 부분해결 붙이는 걸로 알고 있는데요...

    댓글 작성하기 좋아요0 댓글수1
    •  
      최기자 Lv.4 2020.01.16

      안녕하세요! 교수님하고 상의해 봐야 해요~. 지금까지 부분해결을 몇 번 문제까지 풀었을 때까지로 볼 지는 교수님께서 결정하셨거든요~! 여쭤볼게요!

      좋아요0
  •  
    리프 Lv.6 2020.01.16

    일단 제가 생각하는 접근 방법은 1번 증명에서 실제로 존재할 수 없는 정삼각형의 조건을 구해서 그러한 정삼각형의 개수를 T(n)에서 빼는 방식으로 접근하고 있습니다.

    (대략적인 접근 방법은 길이가 최대인 선분과 나머지 점들간의 관계를 통해서 접근해봤습니다.)

     

    근데 그렇게 강력한 조건은 나오지 않고 존재할 수 없는 정삼각형의 개수가 일차식 형태로 자꾸 나와서 별 의미 없는 결과만 계속 나오네요... 

    1번 풀이에서 '모든 선분당 정삼각형이 최대 2개씩 존재한다' 라는 것을 이용해 상당히 넓은 범위를 잡아서 범위를 쉽게 줄일 수 있을 것이라고 생각해서 이렇게 접근해봤는데 다른 아이디어 있으면 공유 좀 해주시면 좋겠습니다.

     

    (사실 여기까지 적어놓은 내용이 너무 당연한 내용이라 도움이 안 될 것 같지만 일단 올려봅니다.)

    댓글 작성하기 좋아요0 댓글수2
    •  
      구머 Lv.4 2020.01.16

      제가 생각한 접근은, 

      어떤 점 A가 존재하여, A를 포함하는 정삼각형의 개수가 n/2보다 작은 A가 항상 존재할 때, 명제가 자동 성립하게 됩니다. 또, 이러한 A를 찾기 위해, n개의 점들을 모두 포함하는 볼록다각형을 하나 잡아서, 이 다각형의 꼭짓점들 중 하나가 저 조건을 만족하지 않을까? 라는 생각을 하고 있는데..아직 요 부분은 확신이 서질 않네요ㅜㅜ

      좋아요0
    •  
      cube120 Lv.5 2020.01.16

      구머님 아이디어가 맞는 것 같습니다. 힌트를 얻으니 풀기가 한층 쉬워졌습니다. 역시 구머님이네요

      좋아요0
  •  
    부분해결
    cube120 Lv.5 2020.01.16

    3번 풀이입니다. 좀 길어서 한글파일로 적었습니다. 풀이의 핵심은 x를 포함하는 정삼각형의 개수가 n/2보다 작은 점 x가 항상 존재한다는 것을 보이는 것 입니다. (구머님의 아이디어입니다)

    /resources/comment/2020/01/b7942fb8895775f421e01d97f69c0196.hwp 

    댓글 작성하기 좋아요0 댓글수9
    •  
      리프 Lv.6 2020.01.16

      와 벌써 푸시네요 ㄷㄷ 저는 이제 구머님의 아이디어 보고 생각 중이였는데 이미 풀려 있어서 좀 허무하네요 ㅋㅋ

      좋아요0
    •  
      리프 Lv.6 2020.01.16

      풀이도 다 이해가 되는데 구머님 아이디어가 아직도 이해가 잘 안 되네요 ㅠㅠ

      자명하다고 적어 놓으셨는데 어떤 점 A를 포함하는 정삼각형이 n/2보다 작은 A가 존재하면 왜 성립하는거죠?

      잘 이해가 안 되서 친절하게 알려주시면 감사하겠습니다 ㅠㅠ

      좋아요0
    •  
      cube120 Lv.5 2020.01.16

      수학적 귀납법으로 하면 됩니다.

      점이 n개 있는 집합 P_n에 대해 T(P_n) <= n^2/4라고 가정합시다.

      P_(n+1) 에서 tr(x) <= n/2인 점 x가 존재하므로,

      T(P_{(n+1)}) = T(P_{(n+1)}\setminus \left \{ x \right \})+\mathrm{tr}(x) \le \frac{n^2}{4} + \frac{n}{2} \le \frac{(n+1)^2}{4}

      가 되어 n_1일 때에도 성립합니다.

       

      좋아요0
    •  
      리프 Lv.6 2020.01.16

      근데 x를 제외한 집합에서 귀납가설을 적용할 수 있는 이유가 무엇인가요? x를 제외하면 tr(P)<=n/2인 점 P가 존재한다는 보장이 없을 것 같은데요...

      좋아요0
    •  
      리프 Lv.6 2020.01.16

      아 혹시 문제 3 명제를 귀납법으로 보이는 건가요?

      좋아요0
    •  
      구머 Lv.4 2020.01.17

      일단 cube님 풀이는 맞는 것 같아요. (diam이라는 표기를 배우고 갑니다dd)

      좋아요0
    •  
      구머 Lv.4 2020.01.17

      3번에서 제 아이디어가, "점 n개 중에서 1개를 잘 고르면 그 점을 포함하는 정삼각형어요의 개수가 n/2개 이하이도록 할 수 있다"였구, 요걸 큐브님이 잘 처리해줬어요.

       

      그리고 저 명제로 3번을 귀납적으로 보일 수 있는거죠.

      좋아요0
    •  
      리프 Lv.6 2020.01.18

      구머님 아이디어는 볼 때마다 정말 대단한 것 같네요 ㄷㄷ

      사실 cube님 풀이에서 첫 번째 케이스와 두 번째 케이스로 나누는 것과 첫 번째 케이스 풀이까지 거의 비슷하게 접근했었는데 이 때 나온 일차식 형태의 정삼각형 개수를 단순히 이차식이 아니라서 의미 없다고 생각하고 넘겼었네요 ㅋㅋㅋㅋㅋㅋㅋ

      핵심적인 아이디어를 제공한 구머님과 풀이를 완성한 cube님 둘 다 정말 대단합니다 ㄷㄷㄷㄷ

       

      (근데 diam이라는 표기가 점들의 집합에 존재하는 최대 길이의 선분을 뜻하는 것 맞나요? 저는 그렇게 이해했는데 만약 다르면 알려주시기 바랍니다)

      좋아요0
    •  
      cube120 Lv.5 2020.01.18

      맞아요. 기호는 지름(Diameter)을 줄인 말이기도하고요.

      원의 지름이 원 위의 두 점 사이 최대 거리라는 것을 생각해보면 자연스러운 정의라는 것을 알 수 있습니당!

      좋아요0
  •  
    무한대의끝을본남자 Lv.6 2020.01.17
    확인요청중

    1. T(n)\leq \frac{n^2}{3}

    I.T(3)일때

    모두가알듯이이런모양이다

    즉 1이다 부등식도 성립된다

    II.T(4)일때

    방금 모양에서 점 1개를 추가한최대모양이다

    T(3)일때 정삼각형의 한변의 길이를 n이라고 하자

    그리고 각각의점을 D_1,D_2,D_3,D_4라고가정하자

    D_1D_3=n,D_1D_2=n,D_2D_3=n이다

    D_4를추가했을때

    모두길이 n에 벗어난다면 정삼각형은 1개밖에없다

    다른정삼각형이되는조건 3개로 하려면D_1=D_4orD_2=D_4orD_3=D_4

    즉 남은 조건한가지는 이다

    이런식으로 계속해나가다가

    정육각형이만들어지는데 정육각형을 계속반복하여 벌집모양으로 배열하면(??????)

    최대한의 삼각형이만들어지는데 벌집모양이 최대로 정삼각형을 만들수있는이유는 너튜브의 수학영상(교수님의)에기제되어있다

    이제 식을만들어보자,  T(n)=n-2이/가 된다

    이제 이를 대입하여보자 아, 참고로 이방법말고도 조합론적으로

    정삼각형\subset예각삼각형이다 

    조합론적으로 해석하여 예각삼각형 = 삼각형 - 둔각삼각형-직각삼각형 이런식으로

    조합론적(확률론)으로 풀수도있다

    n-2 \leq \frac{n^2}{3}임은 쉽게 유도할수있으므로 여백이부족<ㅍㅍㅍ 하여 증명하지않겠다

     

     

     

    댓글 작성하기 좋아요0 댓글수1
    •  
      cube120 Lv.5 2020.01.18

      일단, T(n)=n-2인 이유를 모르겠습니다. 예를 들자면 T(6)=5, T(7)=8, T(8)=10 이기 때문에 n>5부터는 식이 성립하지도 않구요.

      게다가 문제의 흐름을 보면 알 수 있듯이 T(n)는 n에 대한 이차식에 비례하는, 즉 O(n^2)입니다. 따라서 T(n)을 일차식으로 나타낸거 자체가 틀렸습니다.

      좋아요0
  •  
    무한대의끝을본남자 Lv.6 2020.01.17
    확인요청중

    3. \lim_{n     o \infty }\frac{T(n)}{n^2}\leq 0.25

    우리는 방금 T(n) = n-2인것을 알았음으로

    이를 쉽게풀수있습니다

    이는 극한의 기본성질의따라

    \lim_{n \rightarrow \infty }\frac{n-2}{n^2}=\lim_{n\rightarrow \infty}\frac{n}{n^2}+\lim_{n\rightarrow \infty}\frac{1}{n^2}=0+0=0이므로 성립한다

    댓글 작성하기 좋아요0 댓글수2
    •  
      구머 Lv.4 2020.01.17

      에구 T(n)이 n-2가 아니에요ㅜㅜ (간단하게 n=7일 때 정육각형 배치가 정삼각형 개수가 최대가 되는데, 이때 정삼각형이 8개가 되요)

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.01.18

      저도틀렸다는것을알았지만 수정버튼이없어 수정할수가없는사실

      좋아요0
  •  
    무한대의끝을본남자 Lv.6 2020.01.18
    확인요청중

    1번문제가 해결되었지만

    저만의 방법으로 다시풀겠습니다

    1. T(n)\leq \frac{n^2}{3}임을 증명하세요.

    일단 몇가지사실을 알아둡시다

    a\leq b\leq c가성립하려면 a\leq c,b\leq c가성립되어야한다

    여기서 a=T(n),b=\frac{n^2}{3},c=\binom{n}{3}이라고가정하자, T(n)\leq \left \binom{n}{3}임은 조합론에서 자명하다(\binom{n}{3}은 n개의 점중에 3개를선택해서 삼각형을만드는수)

    그리고 b\leq c임은 \binom{n}{3}=\frac{n!}{3!(n-3)!}=\frac{n*n-1*...*1}{3!*n-3*n-4*...*1}=\frac{n*n-1*n-2}{6}=\frac{n^3-3n^2+2n}{6}으로 쉽게 알수있다

     

     

    다른증명

    \frac{n^2}{3}< T(n)이라 명제를 꼬자

    T(3)=1인것은 정설이다

    3<1이아니므로 모순이생겨참이다

    댓글 작성하기 좋아요0 댓글수5
    •  
      리프 Lv.6 2020.01.18

      a<c와 b<c가 성립해도 a와 b의 대소는 알 수 없습니다.

      그리고 두 번째 증명에서 귀류법 형태로 접근하신 것 같은데 주어진 명제의 부정은 '어떤 자연수 n이 존재하여 n^2/3<T(n)을 만족한다'이므로 T(3)<3인 것은 문제가 되지 않습니다.

      좋아요0
    •  
      cube120 Lv.5 2020.01.18

      무끝남 님 다음의 증명이 어디가 틀렸을까용

       

      명제) 리만 가설은 참이다. (즉, 리만 제타 함수의 모든 비자명 근의 실수부는 1/2이다.)

      증명) 명제를 꼬자. -> 리만제타함수의 비자명 근의 실수부는 1/2가 아니다.

      그런데 첫번째 비자명근의 실수부는 1/2이다. ->  모순

      따라서 리만 가설은 참이다.

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.01.20

       

      귀류법형식으로 접근한것이

      p-->~q가 거짓이다를 증명하여

      P-->q가참임을 명제의 성질로 증명했는데 뭐가틀린걸까요?

      혹시 제가 안배운걸수도있습니다

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.01.20

      아니요....

      귀류법은 그런식으로 하는것이아니라

      p 는 가정이고 q는 결론입니다

      p랑 q자체가 명제가아니라

      p = 임의의실수n

      q = T(n)<=n^2/3이성립

      여기서 q를 꼬면

      T(n) >n^2/3이성립

       

      제가 한 방식이 맞는데요?

      좋아요0
    •  
      리프 Lv.6 2020.01.20

      '임의의 자연수 n에 대해 명제 p(n)이 성립한다.' 의 부정은

      '어떤 자연수 n이 존재하여 명제 p(n)이 성립하지 않는다.' 입니다.

      지금 님은 명제의 부정을 잘못 잡아서 논리적으로 오류가 발생한 것입니다.

       

      한 번 님의 논리대로 '모든 소수는 3이다'를 증명해보겠습니다.

      명제를 꼬자(?)

      모든 소수는 3이 아니다.

      그런데 3은 소수다. 따라서 모순.

      따라서 모든 소수는 3이다.

       

      이제 어디가 틀렸는지 이해가 되시나요?

      좋아요0
  •  
    Lv.10 2020.01.20

    뭐가 잘못됬나요?

    1번 풀다가 망했어요 ㅠㅠ

    댓글 작성하기 좋아요0 댓글수1
    •  
      리프 Lv.6 2020.01.20

      nC3이 n^2/3보다 작다는 것을 보이려고 한 것부터가 접근이 잘못되었습니다.

      nC3은 삼차식이고 n^2/3은 이차식이므로 적당한 자연수 N이상부터는 nC3이 반드시 커지게 되므로 그 방식으로 접근할 수 없습니다.

      좋아요0
  •  
    mathwizard Lv.7 2020.01.21

    소문제 몇 번이 해결되고, 몇 번이 해결되지 않았나요?

    댓글 작성하기 좋아요0 댓글수4
    •  
      리프 Lv.6 2020.01.22

      구머님이 핵심 아이디어를 제공해주셔서 cube님이 구머님의 아이디어를 바탕으로 2,3,4번을 모두 해결했습니다.

      좋아요0
    •  
      mathwizard Lv.7 2020.01.22

      리프님이 1번도 해결한 거 아니었나요?

      좋아요0
    •  
      리프 Lv.6 2020.01.23

      저는 1번만 풀었고 나머지는 cube님이 풀었어요

      좋아요0
    •  
      최기자 Lv.4 2020.01.28

      교수님께 최종 검토를 요청드리겠습니다.^^

      좋아요0