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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대30. 다면체로부터 얻어지는 수열2

2019.06.03

같이 풀어볼까?

네이버밴드 구글플러스

다면체(polyhedron)란 3차원 공간상에 있는 유한개의 점의 볼록포(convex hull)로 정의된다. 가령 3차원 공간상에 네 개의 점이 한 평면 위에 있지 않으면 그 점으로 만들어지는 다면체는 사면체다.

다면체  중에서 모든 면이 삼각형인 다면체는 단체다면체(simplicial polyhedron)라 부른다. 지난 2019년 1월의 문제(대25. 다면체로부터 얻어지는 수열)에서 다면체의 조각수열이라는 것을 정의했다.

 

[정의] 단체다면체 P조각수열

다면체의 f_{0}=m개의 점 중 j개의 점으로 이뤄진 부분집합 T를 생각하고, 단체다면체 P로부터 유도되는 그래프 G_{T}를 생각하자. T의 두 점이 P에서 변으로 연결돼 있다면 이 두 점은 G_{T}에서도 변으로 연결된다. 이때 G_{T}는 몇 개의 연결된 조각으로 나뉘는데 이 연결성분의 개수를 cc(G_{T})라 하자. 이제 수열 \left \{ b_{j} \right \}를 다음과 같이 정의한다.

b_{j}=\sum_{\left | T \right |=j}\left ( cc\left ( G_{T} \right )-1 \right )=\sum_{\left | T \right |=j}cc\left ( G_{T} \right ) -\binom{m}{j}

일반적으로 j\leq 1 혹은 j\geq m-2인 경우 b_{j}=0이 되므로 \beta \left ( P \right )=\left ( b_{2}, b_{3}, b_{4}, \cdots, b_{m-3} \right )라 하고 이를 P의 조각수열이라 한다.

우리는 이번 달 폴리매스 문제에서 조각수열을 조금 더 다뤄보려 한다. n각쌍뿔이란 밑면이 합동인 두 개의 n각뿔의 두 밑면을 붙여서 만든 도형이다. 가령 육각쌍뿔의 모양은 다음과 같다.

우리는 이미 오각쌍뿔의 조각수열이 (6, 5, 0)이며 육각쌍뿔의 조각수열은 (10, 16, 9, 0)임을 보인 바 있다. 이를 일반화해 보자.

 

문제 1-1 n각쌍뿔의 점의 개수는 m=n+2다. b_{2}와 b_{m-3}=b_{n-1}의 값을 각각 구하라.

문제 1-2 자연수 n이 4보다 클 때, 다음이 성립함을 증명하라.

b_{m-4}=b_{n-2}=\binom{m-3}{2}-1

 

문제 2 자연수 3\leq k\leq n-2에 대해 n각쌍뿔에서 b_{k}의 값을 n과 k에 대한 식(혹은 mk에 대한 식)으로 나타내라.

 

한편, 문제 1-1에서 주어진 도형의 b_{m-3} 값을 계산했다. 그 값이 가지는 의미에 대해 생각해 보자. b_{m-3} 값이 양수가 된다는 것은 m-3개를 골랐을 때 그것으로 인해 만들어지는 G_{T}가 두 개 이상의 연결 조각으로 나뉜다는 뜻이다. 즉, 이때 나머지 3개의 점으로 구성된 \overline{T}에 대해 G_{\overline{T}}를 생각하면, G_{\overline{T}}는 반드시 삼각형이 됨을 알 수 있다. 따라서 b_{m-3}의 값이 0이 되기 위한 필요충분 조건은 P의 선분으로만 구성된 그래프에서 길이가 3인 사이클(cycle)은 반드시 P의 면이 돼야 한다는 것과 동치다.

 

문제 3-1 b_{m-3}=0일 때, b_{m-4}가 가지는 조합적 의미는 무엇일지 생각해 보자.

문제 3-2 b_{m-3}=0을 만족하는 도형 중에서 b_{m-4}의 값이 가장 큰 도형은 무엇일까.

 

 

댓글 17

  • Undefined 2019.06.03 16:31:01

    인천 오일러 분이 25번 문제에서 위, 아래 꼭짓점을 고른 한 가지와 n각형의 대각선 수를 합해 b_2 = 1+\frac{n(n-3)}{2}임을 보였습니다.

    좋아요0 댓글수0
  • Undefined 2019.06.03 16:41:12

    b_{m-3}은 세 점을 제거하는 것이다.

    여기서 꼭짓점은 각 각뿔의 밑면 밖에 있는 한 점을 말한다. 또, 가운데는 각 각뿔의 밑면이라는 뜻으로 사용되었다.

    i) 꼭짓점 2개와 가운데 1개를 제거하는 경우: 연결그래프 유지

    ii) 꼭짓점 1개와 가운데 2개를 제거하는 경우: 나머지 꼭짓점에 의해 연결그래프 유지

    iii) 가운데에서만 3개를 제거하는 경우: 두 꼭짓점이 연결되어 있는 경우와 아닌 경우로 나뉜다.

        (1) n=3    b_{m-3}=1

        (2) n>3    b_{m-3}=0

    좋아요0 댓글수0
  • Undefined 2019.06.03 17:10:28

    점 4개를 제거해서 연결그래프가 아닌 그래프를 만드려면 꼭짓점을 제거해야 한다.

    꼭짓점이 남아있으면 그에 의해 다른 점들이 모두 연결된다.

    따라서 n각형에서 두 점을 제거하는 것과 같다.

    두 점은 연속하면 안되므로 b_{n-2}는 대각선의 수인 \frac{n(n-3)}{2}이다.

    (??? 문제와 다르다 ???)

    좋아요1 댓글수3
    • 데넵 2019.06.03 22:35:35

      앗, 문제에 오타가 있네요. 죄송합니다. ^^;

      수식에서 n이 아니라 m이어야 합니다.

      좋아요0
    • 데넵 2019.06.03 22:39:04

      그래서 문제는

      b_{m-4}=b_{n-2} = \binom{m-3}{2}-1 = \frac{n(n-3)}{2}

      로 바뀌어야 합니다. 잘 푸셨어요~

      좋아요0
    • 김우현 기자 2019.06.24 09:23:45

      교수님께서 직접 검토해주셨네요.

      Undefined 친구가 소문제 1-1, 1-2번 문제를 해결했습니다~. laugh

      좋아요0
  • 최영준 기자 2019.06.04 09:00:16

    문제 1-2에 오타가 있었습니다. 죄송합니다 여러분.

    n-3을 m-3으로 수정해야 하네요. 다시 수정했습니다.

    혼동을 드려 죄송합니다^^

    계속 열심히 풀어주세요~!

    좋아요0 댓글수0
  • 모두다같이 2019.06.05 19:07:34

    우와 또 다면체다룬 수열이다..

    좋아요0 댓글수0
  • Undefined 2019.06.08 17:44:46

    문제 2

    b_i =\left ( \sum_{k=1}^{min(i,n-i)}(n-k)\binom{i-1}{k-1}\binom{n-i-1}{n-i-k} \right )-\binom{n}{i}

    풀이

    좋아요0 댓글수4
    • Undefined 2019.06.10 15:56:27

      계산 오류가 있었네요.

      (n-k)가 아니라 n입니다.

      수정된 풀이 올립니다.

      b_{i}=n\left ( \sum_{k=1}^{min(i,n-i)}{\binom{i-1}{k-1}\binom{n-i-1}{k-1}} \right )~-\binom{n}{i}

      식을 더 단순화 할 수 있지 않을까요???(HOW?)

      좋아요0
    • 구머 2019.06.10 20:26:35

      저거 생성함수로 한번 시도해보실래요?

      좋아요0
    • 수학장 2019.06.18 19:59:36

      저런 문제는 항상 생성함수가 따라다니네요...

      좋아요0
    • 구머 2019.06.22 11:21:31

      \sum _{k=1}^{min(i,n-i)}\binom{i-1}{k-1}\binom{n-i-1}{k-1}=\sum _{k=1}^{min(i,n-i)}\binom{i-1}{k-1}\binom{n-i-1}{n-i-k}니까, 이 식은 n-2개의 공에서 n-i-1개의 공을 뽑는 경우의 수와 동치입니다!!. 따라서 위 식은 \binom{n-2}{n-i-1}=\binom{n-2}{i-1}로 변형되고, b_i=n \binom{n-2}{i-1}-\binom{n}{i}가 됩니다.(근데 이럼 크기관계가 이상한데..)

      좋아요0
  • Undefined 2019.06.10 19:47:56

    A_{\infty}=(0,0,1),  A_{-\infty}=(0,0,-1)이라고 하자.

    A_{1,0}=(1,0,0),  A_{2,0}=(-1,0,0),  A_{3,0}=(0,1,0),  A_{4,0}=(0,-1,0)이라고 하자.

    또, 어떤 작은 각 \theta와 충분히 더 작은 길이 \epsilon, 수 N\left(N\theta<\frac{\pi}{2}\right) 을 정해 \left ( i \in \mathbb{Z},~-N\leq i\leq N\right )에 대해 다음과 같이 점들을 정의하자.

    A_{1,i}를 A_{1,0}을 y축에 대해 \pm i\theta회전시킨 점 중 z좌표의 부호가 i의 부호와 같은 점이라고 하자. 마찬가지로 A_{3,i}를 정의하자.

    A_{2,i}를 A_{2,0}을 x축에 대해 \pm i\theta회전시킨 점 중 z좌표의 부호가 i의 부호와 같은 점을 원점 방향으로 \epsilon 만큼 움직인 점이라고 하자. 마찬가지로 A_{4,i}를 정의하자.

    그러면 위에서 정의된 모든 점들의 볼록포는 약간(\epsilon 만큼) 일그러진 사각뿔대를 xy평면에서 멀어질수록 점점 줄어드는 모양으로 쌓은 모양이다.

    이 도형의 b_3 =0이고 b_4 \geq 2N+1이다. 

    따라서 3-2번 문항에서 b_4의 상한은 \infty이다.

    좋아요0 댓글수2
    • Undefined 2019.06.10 20:01:50

      이해를 돕기 위한 사진

      좋아요0
    • 데넵 2019.06.11 14:58:13

      네... ^^;; $m$이 무한히 커지면 b_i값이 무한히 커지는 도형이 있는건 사실인데...

      문제의 의도는 $m$을 고정시켰을때 가장 큰 도형이 무엇인지 묻는 것이었습니다. ^^;; 질문을 다소 모호하게 적었었네요... 죄송합니다.

      좋아요0
  • 수학장 2019.06.18 19:58:23

    3-1번 문제 : b_{m-3} = 0이라는 것은, 임의의 3개의 점으로 구성된 그래프가 그 다면체의 면이 된다는 의미이다.를 증명을 하고 있었는데 서문에 나와 있었네요... 뭐하는 짓이지.... 아무튼 b_{m-3}=0일 때, b_{m-4}=0이라면, P이 선분으로만 구성된 그래프에서 길이가 4인 임의의 그래프(이하 G_S)는 반드시 P의 면 2개가 돼야 합니다. 면이 2개보다 적다면 G_S가 그 자체로 면이 되어야 한다는 뜻인데, 단체다면체의 정의에 모순. 면이 2개보다 많다면 면들 사이에 교점이 1개 이상 있다는 뜻이다. 그러면 그 교점이 교점과 G_S를 제외한 나머지 그래프와 독립되므로 b_{m-4} \neq 0. 그러면 당연하게도 b_{m-4}가 양수라는 것은 G_S가 면 2개로 이루어지지 않았다는 것과 동치.

    좋아요3 댓글수0