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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대6. 다면체 색칠하기

2017.06.01

같이 풀어볼까?

네이버밴드 구글플러스

모든 면이 삼각형으로 된 다면체를 단체다면체(simplicial polyhedron)이라고 부른다. 각 다면체의 꼭짓점에 7개의 벡터\left \{ \begin{pmatrix} 1\\0\\0 \end{pmatrix},\, \begin{pmatrix} 0\\1 \\0 \end{pmatrix}, \, \begin{pmatrix} 0\\0\\1\end{pmatrix},\, \begin{pmatrix}1\\1 \\0 \end{pmatrix}, \,\begin{pmatrix}1\\0 \\1\end{pmatrix}, \, \begin{pmatrix} 0\\1 \\1 \end{pmatrix}, \, \begin{pmatrix}1\\1 \\1 \end{pmatrix} \right \}를 사용해 다음 두 규칙을 모두 만족하도록 색칠하는 것을 좋은 색칠이라 하자.

 

(1) 각 변으로 연결된 두 꼭짓점은 같은 벡터로 칠할 수 없다.

(2) 다면체의 각 면의 세 꼭짓점에 칠해진 세 벡터를 v_1,\, v_2,\, v_3라 할 때, v_1+ v_2+ v_3의 모든 성분이 짝수가 아니다.

예를 들어 \begin{pmatrix} 1\\ 0 \\0 \end{pmatrix}, \, \begin{pmatrix} 0\\0 \\1 \end{pmatrix}, \, \begin{pmatrix}1\\ 0\\ 1\end{pmatrix}는 그 합이 \begin{pmatrix}2\\0 \\2 \end{pmatrix}이고 모든 성분이 짝수이므로, 이 세 벡터로 색칠된 삼각형은 좋은 색칠인 단체다면체의 면이 될 수 없다.

 

질문1. 정사면체의 좋은 색칠의 가짓수(A)는 몇 가지인가?

 

질문2. {\color{DarkBlue} n}각쌍뿔 ( {\color{DarkBlue} n}-gonal bipyramid)란 두 개의 각 뿔의 밑면을 붙여서 만든 단체다면체다. {\color{DarkBlue} n}각쌍뿔의 좋은 색칠의 가짓수를 Bn이라 하고, 질문1에서 구한 답을 A라고 할 때 이 둘을 나눈 값 {\color{DarkBlue}\frac{B_n}{A} }을 구하여라.

질문2-1. 질문 2가 너무 어렵다면 오각쌍뿔의 좋은 색칠의 개수를 B라 할 때 B/A의 값을 구해보세요.

 

질문3. 임의의 단체다면체는 좋은 색칠이 존재함을 4색 정리를 사용해 증명하여라.

 

질문4. 임의의 단체다면체는 좋은 색칠이 존재함을 4색 정리를 사용하지 않고 증명하여라.

 

※알립니다.

질문 1, 2, 3번이 해결됐습니다. 출제자인 최수영 아주대 수학과 교수는 shine과 누군가, 수돌이 선수가 모두 문제를 잘 해결해 줬다고 밝혔습니다. 특히 질문 2에 관해서 수돌이 선수의 아이디어와 점화식 모두 맞았다고 밝혔습니다. 문제를 출제할 때부터 점화식을 세우는 데까지만 기대했기 때문에 점화식을 푼 결과와 별개로 질문 2는 해결됐다고 본다고 이야기했습니다.

이제 남은 건 질문 4입니다. 질문3에 의하면 이 문제는 참이지만, 알다시피 4색 정리는 매우 복잡한 경우를 나누어서 각 경우를 컴퓨터로 계산해 증명한 정리입니다. 우리의 경우는 4색이 아니라 7개의 색을 색칠할 수 있으므로 4색 정리를 쓰지 않고 직관적인 논리전개 만으로도 해결 할 수 있으리라 생각합니다. 그런데 의외로 그 풀이가 알려져 있지 않습니다. 여러분들이 한 번 그 답을 찾아보세요!

 

 

댓글 10

  • shine 2017.06.03 09:20:22

    일단 1번은 168가지네요 풀이는 지금 급해서 나중에 하겠습니다.

    좋아요0 댓글수0
  • 누군가 2017.06.06 13:47:43

    질문1.

    2번조건이 뭔가 애매한데 V1+V2+V3의 모든 성분이 홀수여야 한다면

    V1+V2+V3의 모든 성분이 홀수인 세 벡터는 두 벡터가 정해지면 나머지 하나는 자동으로 정해진다.

    (주어진 벡터를 순서대로 1,2,3,4,5,6,7이라 하면 (1,2,3)(1,4,5),(2,4,6)(3,5,6) 밖에 없다.)

    그런데 정사면체 ABCD에서 A,B가 정해지면 C=D가 되는데 이는 조건1에 위배된다.

    따라서 V1+V2+V3의 모든 성분이 홀수여야 한다면 없다.

    좋아요0 댓글수3
    • 누군가 2017.06.06 13:51:12

      조건2에서 적어도 하나가 홀수라 생각하면

      먼저 정사면체의 모든 꼭짓점은 연결되있으므로 조건1에 의해 각 꼭짓점이 같은 벡터를 가질 수는 없다.

      그러면 조건1만 고려했을 때 정사면체를 칠할 수 있는 벡터의 조합은 7개의 벡터중 4개를 선택하는 7C4=35 가지이다.

      주어진 7개의 벡터를 다 더하면 (4,4,4)이므로 V1+V2+V3의  모든 성분이 짝수인 3개의 벡터를 고를 수 있는 수를 35가지에서 빼주면 된다.

      주어진 백터를 순서대로 1,2,3,4,5,6,7 이라 하면 V1+V2+V3의  모든 성분이 짝수인 3개의 백터의 순서쌍은

      (1,2,4)(1,3,5)(1,6,7)(2,3,6)(2,5,7)(3,4,7) 6가지이다.

      35-6=29 29가지

      여기서 고려하지 않은게 정사면체ABCD에서 A가 위로 오게 두었을 때 밑면의 꼭짓점을 시계방향으로 읽었을 때 밑면이 BCD인것과 BDC 인것과 다르다는 점이다.(A-BCD랑 A-BDC)이걸 고려하면 29*2=58

      좋아요0
    • shine 2017.06.06 17:34:20

      그런 방식으로 푼다면 돌리거나 뒤집어서 같은 것을 하나로 센다는 말이 없으므로 7C4 가 아닌 7P4 입니다.

      또 V1+V2+V3의 모든 성분이 짝수인 3개 벡터로 가능한 경우에서 (4,5,6)을 빼먹으셨더군요. 따라서 7가지 입니다.  그런데 여기서도 돌리거나 뒤집어서 같은 것을 하나로 보는게 아니므로 제대로 경우를 구하면

      ( 3개 말고 다른 벡터 하나가 오는 꼭짓점의 종류)×( 그 벡터 하나가 가능한 종류)×(3개 벡터의 배치)×7 이 되어 총 경우는

      7P4 - 4×4×3!×7 = 840-672=168가지가 됩니다.

       

      좋아요0
    • 누군가 2017.06.07 01:31:05

      음.. 그러네요.

      그리고 제가 위에 써놓은 것도 아예 틀렸네요.

      먼저 4개짜리 조합만 생각하면 35가지인데 합이 짝수가 되는 3개 짜리 조합 7가지를  뺀다고해서 조건에 남는 조합만 남는게 아니더라고요. 오히려 짝수가 되는 조합의 수만큼만 가능합니다. 전체 벡터 합에서 짝수 조합 합만 빼면 짝수 성분만 남는데 모든 성분이 짝수인 벡터는 없음으로 나머지 네 벡터 중 하나를 뺐을때 항상 홀수인 성분이 하나 이상 나옵니다. 짝수가 되는 3개짜리 조합말고 다른 조합을 빼면 나머지 4개에서 항상 짝수조합이 나옵니다.(왜그런지는 정확히 모르겠지만) 그래서 돌리거나 뒤집어서 같은 것을 하나로 센다면 7*2=14가지  하나로 세지 않는다면 7*4!=168가지. 맞네요.

      좋아요0
  • 누군가 2017.06.12 02:46:37

    질문3

    A-4색정리가 결국 '모든 평면 그래프의 꼭짓점을 많아봐야 네 가지 색만 사용하여 인접한 꼭짓점들이 같은 색을 가지지 않도록 칠할 수 있는가'이다. (위키백과에 따르면)

    B-4개 중 어떤 3개를 골라도 조건2에 위배되지 않은 쌍이 있다.(7개의 벡터에서 세쌍짜리 짝수 조합7개를 뺀 네쌍 조합 7개)(예로 들면 1247)

    C-단체 다면체의 한면을 제일 바깥쪽으로 나가도록 늘려 평면으로 만든다고 생각하면 항상 평면그래프로 만들 수 있다.

    (예시로 문제에 있는 6각쌍뿔을 평면그래프로 바꾼 그림)

    D-(A,C에 의해)단체 다면체를 연결상태가 같은 평면 그래프로 바꿀 수 있으므로 네 가지 벡터만 사용하여 인접한 꼭짓점들이 같은 벡터를 가지지 않도록(조건1에 위배되지 않도록) 할 수 있다.

    따라서 (B,D에 의해)임의에 단체다면체는 좋은 색칠이 존재한다.

    좋아요0 댓글수0
  • 수돌이 2017.06.15 20:24:04

    질문 6-2 해결:

    정답:

    B_n=7(4^n+2(-2)^n))+42(\frac{2\sqrt{21}(1+\sqrt{21})}{105})((\frac{1-\sqrt{21}}{2})^n+\frac{(\frac{1-\sqrt{21}}{2})^{n+2}}{4}) +(\frac{2\sqrt{21}(\sqrt{21}-1)}{105})((\frac{1+\sqrt{21}}{2})^n+\frac{(\frac{1+\sqrt{21}}{2})^{n+2}}{4})+4n+7-2(-1)^n)

    그리고 질문 1에 의해 A=168

     

    풀이

    좋아요0 댓글수0
  • shine 2017.06.30 15:35:07

    문제4에 대한 아이디어를 말해보겠습니다.

    3개의 점 B,C,D 와만 연결된 점 A가 있다고 합시다. 그러면 점 A를 무시할 수 있습니다. A와 연결된 점 3개에 어떤 벡터가 오든 \bigtriangleup ABC, \bigtriangleup ACD, \bigtriangleup ADB 와 점 A가 규칙을 만족하게 하는 벡터를 찾을 수 있기 때문입니다. 

    (증명: 점 B,C,D의 벡터를 각각 v_{B}, v_{C},v_{D} 라 하면,

     i) v_{B}+ v_{C}+v_{D} 의 모든의 모든 성분이 짝수일때

     A에 v_{B}, v_{C},v_{D} 외의 어떤 벡터도 가능

     ii) v_{B}+ v_{C}+v_{D} 의 모든의 모든 성분이 짝수일때

    v_{B}+ v_{C}+v_{D} 의 모든 와 각 성분의 기우성이 같은 벡터를 A에 넣으면 성립함)

     

    이는 점 4개와만 연결된 점에서도 가능합니다.

     

    (일단 \mathbb{T}=\left \{ \begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ 0 \end{pmatrix}, \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix},\begin{pmatrix} 0\\ 0\\ 1 \end{pmatrix},\begin{pmatrix} 1\\ 1\\ 0 \end{pmatrix},\begin{pmatrix} 1\\ 0\\ 1 \end{pmatrix},\begin{pmatrix} 0\\ 1\\ 1 \end{pmatrix},\begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix}\right \}라 하고,

    \mathbb{T}의 원소를 대상으로 하는 연산 ⊕을 다음과 같이 정의하자.

    ''P⊕Q 는 \mathbb{T}의 원소 중 P+Q와 각 성분의 기우성이 같은 벡터이다.''

    이때 연산 ⊕는 결합법칙과 교환법칙이 성립한다.

     

    본 증명

    위와 같이 점 A가 점 B,C,D,E와 모서리로 연결되어 있을때,

    점 B,C,D,E의 벡터를 

    좋아요0 댓글수1
    • shine 2017.06.30 15:39:26

      나중에 수정하겠습니다.

      좋아요0
  • 구머 2017.09.20 22:15:42

    <묻힌 문제 살리기 프로젝트>

    좋아요0 댓글수0