본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[폴리매스 문제] 대32. 회로가 없는 색칠
수학동아 2019.08.03

 

다면체 중 모든 면이 삼각형인 다면체를 단체다면체라고 한다. 단체다면체는 삼각형으로 이뤄진 평면그래프로 나타낼 수 있다. 정사면체를 평면그래프로 나타내면 아래와 같다. 모든 사면체의 평면그래프는 정사면체의 평면그래프와 같다. 이렇게 두 단체다면체를 나타내는 평면그래프가 서로 같으면 조합적으로 같다고 한다.

 

 

정사면체(왼쪽)과 정사면체의 평면그래프(오른쪽). 

 

 

1-1. 점의 개수가 4개인 단체다면체는 정사면체 밖에 없음이 알려져 있다. 점의 개수가 5개인 단체다면체는 무엇이 있을지 모두 찾아보아라.

1-2. 점의 개수가 6개인 단체다면체는 모두 몇 개인지 찾아보아라.

1-3. 점의 개수가 7개인 단체다면체는 모두 몇 개인지 찾아보아라.

1-4. 점의 개수가 n개인 단체다면체는 모두 몇 개일까?

 

‘그래프 색칠’은 그래프에서 변으로 연결된 꼭짓점이 서로 다른 색이 되도록 칠하는 것이다. ‘4색 정리’는 임의의 평면그래프를 4개의 색으로 칠할 수 있다는 정리다. 이때 ‘회로가 없는 색칠’은 아래 그림처럼 색칠한 그래프에서 임의의 두 색을 골라 만든 부분그래프에 회로가 없는 것이다.  

 

2-1. 정팔면체를 나타내는 평면그래프는 4개의 색을 이용해 회로가 없는 색칠을 할 수 없음을 보여라.

2-2. 정이십면체를 나타내는 평면그래프는 4개의 색을 이용해 회로가 없는 색칠을 할 수 있음을 보여라.

2-3. 단체다면체를 나타내는 평면그래프가 3개의 색으로 색칠돼 있다. 이 색칠은 반드시 회로가 없는 색칠이 아님을 보여라.

 

3. 정팔면체가 아닌 단체다면체 중 4가지 색을 사용해서는 회로가 없는 색칠을 할 수 없는 도형을 찾아라.  

  •  
    tommy Lv.1 2019.08.03 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      수학장 Lv.3 2019.08.03 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      tommy Lv.1 2019.08.03 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    김우현 기자 Lv.4 2019.08.03

    8월 3일 하루 동안 비밀댓글로 풀이를 달아주세요!

    3일이 지나면 다시 공개로 바꾸겠습니다.laugh

    댓글 작성하기 좋아요4 댓글수0
  •  
    Simon Lv.2 2019.08.03

    2-1 풀이

    사진이 돌아갔네요 죄송합니다.

    가운데 삼각형 회로는 3가지 색을 가져야 하므로 A B C 세가지 색을 가진다고 하겠습니다.

    바깥쪽 3개의 점 중, 2개 이상의 점에 제 4의 색인 D가 들어가 있을 경우에는 바깥쪽 3개의 점에서 2개의 색으로 회로가 구성됩니다.

    1개 이하의 점에 D가 있을경우 WLOG A와 B가 그렇다고 놓겠습니다.

    가운데 사각형 회로가 존재하므로 증명 완료되었습니다

    2-2 풀이

     

    2-3 풀이

    교수님이 말씀하신것과 같이 하나의 삼각형을 삼각형들로 채운 그래프로 생각할 수 있습니다.

    삼각형을 이루는 꼭짓점의 색의 종류는 위에 두 가지로 나뉠 수 있는데 하나는 빨간색 하나는 파란색으로 삼각형을 칠하면 같은 색의 삼각형이 연속할 수 없습니다. 따라서 밑에 보이는 사각형이 생기거나 정사면체가 되는데, 정사면체인 겅우에는 불가함이 밝혀져 있고 그렇지 않은 경우에는 사각형 바깥 보라색 점들로 회로가 생김을 알 수 있습니다. 증명완료.

    도전문제 풀이

    A B C에는 서로다른 색이 칠해져 있어야 합니다. 위 2-3풀이에서 봤듯이 X Y중 하나에는 네번째 색이 칠해져야 합니다. WLOG X

    그러면 Y에 올 수 있는 색은 Y B C 회로와 X B Y회로에서 빨간색밖에 없음을 알 수 있습니다. P의 관점에서 봅시다. X A P Y에서와 P A C에서 P는 검은색임을 알 수 있습니다. 그러면 Q의 관점에서 봤을 때 Q A C Y에 의해 빨간색과 파란색이 안되고 Q A B Y에 의해 검은색이 안되고 Q X Y에 의해 보라색이 안됩니다.

    증명완료

    사실 정팔면체에 삼각뿔 붙이면 되네요

    수돌이님이 n각쌍뿔이(n은 5이상) 성립함을 찾아네셨어요

    댓글 작성하기 좋아요0 댓글수0
  •  
    Undefined Lv.1 2019.08.03

    댓글 작성하기 좋아요0 댓글수1
  •  
    E=mc^2 Lv.1 2019.08.03 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    E=mc^2 Lv.1 2019.08.03 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    수학장 Lv.3 2019.08.03 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    벡터장 Lv.1 2019.08.03

    1-4번 문제에 대한  아이디어 하나 제안하겠습니다.  단체다면체를 생각할 때 베이스가 되는 삼각형을 하나 그려놓고 풀다보면, 점의 개수가 4개인 단체다면체는 3(베이스)+1, 점의 개수가 5개인 단체다면체는 3(베이스)+2 이런식으로 나타납니다. 여기서 베이스 삼각형의 꼭짓점의 개수를 뺀 n-3개위 점의 분배에 따라서 단체다면체가 결정된 다는 것을 알 수 있으며, 이는 a+b=n-3이라고 부정방정식을 세운 후 해 (a,b)의 개수를 찾다보면 규칙이 보이지 않을까 생각해봅니다.

    댓글 작성하기 좋아요3 댓글수4
    •  
      마이구미 Lv.1 2019.08.03

      a와 b가 의미하는게 뭔지 설명해주실수 있나요?

      좋아요1
    •  
      벡터장 Lv.1 2019.08.03

      각각 베이스 삼각형 위와 아래에 분배하는 점의 개수입니다. 위에는 a점 a개, 아래에는 점 b개 이런 방식으로 말이죠. 

      좋아요0
    •  
      벡터장 Lv.1 2019.08.03

      사실 일반화하여 식을 만들긴 했는데, 귀납적으로 푼거라서 확신을 할 수가 없어서 여러분들께 더 좋은 아이디어 부탁드립니다.

      좋아요2
    •  
      마이구미 Lv.1 2019.08.03

      어떤 방법으로 했는지 궁금한데요 간략한 아이디어라도 알려주실수 있나요?

      좋아요0
  •  
    pi314159 Lv.1 2019.08.03 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    아인수타인 Lv.6 2019.08.03

    2-1번 풀이입니다.

     

    회로가 존재하지 않는다고 하고 정팔면체를 일단 그래프로 나타내면 아래그림처럼 된다.

    삼각형을 이루는 것들은 색이 달라야 한다. 그러므로 A, B, C는 각각 R, G, B라고 할 수 있다. 여기서 D=G와 D=Y의 2가지 경우로 나뉘어진다. 만약 D=G라면 E=R또는 Y이다. 그런데 D=R이라면 ABED의 회로가 생겨 모순이다. 그래서 D=Y이고, F=B가 되는데, 이렇게 되면 ACEF의 회로가 생긴다. 그래서 첫번째 케이스는 모순이다. 두번째 D=Y일때를 보자. 그러면 자동으로 E=R이 되고, F=B가 된다. 그런데 이러면 ACEF의 회로가 생겨 이것도 모순이다. 따라서 정팔면체, 색 4개면 항상 회로가 생긴다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    POLYMATH Lv.1 2019.08.03 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    아인수타인 Lv.6 2019.08.03

    진짜닉네임은 sincostan입니다.(폰 없어서 아인수타인님걸로 했습니다.) 1-4의 답을 올리겠습니다.

    4일때1,5일때1,6일때2,7일때5가 나오므로 규칙으로

    1/n-3×\binom{2n-8}{n-4}라고 생각을 했습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    김우현 기자 Lv.4 2019.08.03

    아래 그림 일부를 수정했습니다. 

    참고해주세요!!

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

    정팔면체랑 조합적으로 같으면 정답으로 인정되지 않나요?

    댓글 작성하기 좋아요2 댓글수0
  •  
    Undefined Lv.1 2019.08.03

    3. snub dodecahedron

    (존슨의 다면체 중에 있음)

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

    3번 정이십면체 되나요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      POLYMATH Lv.1 2019.08.04

      2-2문제에 안된다고 나와 있는데요?

      좋아요0
  •  
    tommy Lv.1 2019.08.03

    혹시 구와 위상동형이 아니더라도(예를 들어 토러스와 위상동형) 삼각형으로 이루어진 입체이기만 하면 단체다면체라고 볼 수 있나요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      Undefined Lv.1 2019.08.03

      그러면 볼록포가 아니지 않나요?

      좋아요0
  •  
    Undefined Lv.1 2019.08.03

    회로있어요

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

      저 위에 파란색도 지나야하는거 아닌가요?

      좋아요2
    •  
      Undefined Lv.1 2019.08.03

      아닙니다

      좋아요0
    •  
      뉴턴의 사과 Lv.1 2019.08.03

      파란색 또한 지나야 합니다.

      좋아요0
    •  
      POLYMATH Lv.1 2019.08.04

      파란색 지나야 되요

      좋아요0
    •  
      아인수타인 Lv.6 2019.08.05

      몇개만 선택해서 지나도 되지 않나요? 만약 다 지나야 하는거면 폴리매스데이때 정답(중 하나)이라고 했던 제 답이 오답이 되는데...

      좋아요0
  •  
    누굴까요 Lv.1 2019.08.03 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    Kingsnake Lv.1 2019.08.03

    비밀댓글 입니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    tommy Lv.1 2019.08.03

    (아이디어) 1-4번 문제에 대해 간단한 추측을 하나 올리자면,

    꼭짓점이 n개인 단체다면체의 수 = (n-4)번째 카탈란 수

    가 되는 것 같습니다. 만약 이 추측이 성립한다면 추측을 증명할 방법은 카탈란 수와 관련된 조합론적 문제의 해답들과 단체다면체를 일대일 대응시키거나, 점화식을 이용하는 방법 등이 있을 것 같네요ㅎㅎ

    댓글 작성하기 좋아요0 댓글수3
    •  
      아인수타인 Lv.6 2019.08.03

      오늘 폴리매스데이 때도 제 옆에 sincostan님이 카탈란 수 비슷한 아이디어 냈었던 거 같아요.

      좋아요0
    •  
      tommy Lv.1 2019.08.04

      그렇군요! 혹시 노가다는 어디까지 해보셨나요? 저는 꼭짓점이 4, 5, 6, 7, 8개일 때 단체다면체가 1, 1, 2, 5, 14개 있다는 것까지 세고 포기했습니다ㅠㅠ

      좋아요0
    •  
      아인수타인 Lv.6 2019.08.05

      노가다는 4 5 6 7 개일 때 1 1 2 5까지 했습니다.

      좋아요0
  •  
    집돌이 페렐만 Lv.6 2019.08.03

    참고해도 될 것 같은데요. 

    위에서 정4면체 정8면체 정12면체 정20면체를 이용하면 될 것 같습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    아인수타인 Lv.6 2019.08.03

    3번 문제

     

    답:

     

    풀이: 회로가 존재하지 않는다고 가정해보자. 각 점을 위쪽, 왼쪽부터 차례로 A,B,...,J라고 해 보자.(깜박하고 못 적었긴 했지만 어디가 뭐인지 알 거라고 생각하고 넘어갑니다.) 색은 뭐든 상관없으니 R,B,G,Y라고 하자. 그런데 삼각형 꼭짓점 3개는 무조건 다 다른 색이어야 한다. 왼쪽 위에 삼각형 ABC를 A=R, B=G, C=B라고 하자. (색 B랑 점 B랑 헷갈리지 않도록 주의!) 이 3개는 고정이다. 그런데 여기서 점 D가 G가 될 수도 있고, Y가 될 수도 있다. 이건 경우를 나눠 줄 수밖에 없다. 일단 D=G라고 하자.

    여기서 E=B,Y가 가능하지만, 만약 E=B라면 BCDE가 회로가 되기 때문에 E=Y다. 그럼 자동적으로 F=R, H=R이 나온다. (B,G,Y랑 이웃해 있기 때문) 여기서 G는 G가 될 수도 있고(파랑) Y가 될 수도 있어서(빨강) 경우를 나눠줘야 한다. 파란색의 경우, I=B, J=Y가 나와 EFHJ가 회로, 빨간색의 경우, I=G, J=B가 나와 CFHJ가 회로가 된다. 따라서 첫 번째는 모순이다. 두 번째 D=Y일 경우를 보자.

    여기서는 자동으로 E=B가 나온다. 그리고, F=R,Y가 가능한데, F=R이라면 ACEF, F=Y라면 CDEF가 회로가 되어 모순이 나온다. 따라서 위 도형의 경우, 어떻게 해도 회로가 생긴다.

     

    (참고: 사실상 찍어 놓고 검증한 겁니다. 행사 때 걍 끄적인 게 정답이었네요...)

    댓글 작성하기 좋아요0 댓글수6
    •  
      집돌이 페렐만 Lv.6 2019.08.09

      어느 도형의 평면그래프인지요

      좋아요0
    •  
      아인수타인 Lv.6 2019.08.09

      사각뿔 2개를 비스듬히 해 놓고 그 사이에 정삼각형을 끼워 넣은 도형입니다.

      좋아요0
    •  
      아인수타인 Lv.6 2019.08.19

      아 잠만 아니네요... 사각뿔 2개를 두고 그 사이를 선분으로 연결한 다음, 대각선을 연결한 도형입니다. 근데 이 도형의 면 2개가 평면이 될지 모르겠네요... 이건 연구해보도록 하겠습니다.

      좋아요0
    •  
      집돌이 페렐만 Lv.6 2019.08.19

      ...사각뿔 2개를 두고 사이를 선분으로 연결하고 대각선을 연결하면 단체다면체가 아니지 않나요????coolcrying

      좋아요0
    •  
      아인수타인 Lv.6 2019.08.20

      그게 가운데 나타난 선분 4개로 둘러싸인 영역이 평면이 아니면 문제가 없는데 평면이면 문제가 돼서...

      좋아요0
    •  
      아인수타인 Lv.6 2019.08.21

      아, 근데 다행히 제가 원래 생각했던 도형도 되긴 하네요. 풀이는 같은 원리이므로 생략합니다. 그리고 그건 지나지 않는 부분도 없네요.

      (원래 말했던 '사각뿔 2개를 비스듬히 해놓고 그 사이에 정삼각형들을 끼워 넣은 도형'은 위에 저 도형의 가운데 양쪽의 오른쪽 위에서 왼쪽 아래로 향하는 대각선들을 왼쪽 위에서 오른쪽 아래로 향하는 대각선들로 바꾸면 됩니다.) 

      좋아요0
  •  
    ghost Lv.1 2019.08.04 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    Aquarius Lv.1 2019.08.05

    위 그림에서 꼭짓점 이외에 직선들끼리 교차하는 부분이 생김으로 위 그림은 평면그래프가 아니지 않나요?

    교차하는 부분에도 꼭짓점을 그려주거나(그러면 정 팔면체가 아니므로 이 방법은 제외)

    원래 정팔면체 그래프로 변형하여 풀어야 하나요?

     

     

    댓글 작성하기 좋아요0 댓글수3
  •  
    김우현 기자 Lv.4 2019.08.08

    친구들, 8월 3일이 지났으니 비밀 댓글을 공개해서

    다른 친구들이 볼 수 있도록 해주세요~!!

    댓글 작성하기 좋아요0 댓글수0
  •  
    인천 오일러 Lv.1 2019.08.12

    1-4. 

     오일러 지표를 이용하면 V-E+F=2입니다. 이때 단체다면체이므로 한 면에는 모서리가 3개씩 있고, 그 모서리는 하나당 2면에 걸쳐있으므로 E=\frac{3F}{2}입니다. 이를 다시 원식에 대입하면 V=\frac{F}{2}+2가 됩니다. 이때, 점이 n개 이므로 F=2(n-2) 이고, 다시 E=3(n-2)입니다. (당연히 V=n) 입니다. 

     이때 구하려는 단체다면체와 조합적으로 같은 평면그래프를 나타내는 n차 정방행렬 A를 생각합니다. 이때 A의 i행 j열 성분을 A_{i,j}라 하면 A의 조건은 다음과 같습니다.

    0. A의 모든 성분은 0 또는 1

    1. A_{i,j}=A_{j,i}

    2. A_{i,i}=0

    3.  \sum_{i=1}^{n}\sum_{j=1}^{n}A_{i,i}=\sum_{i=1}^{n}A^{2}_{i,i}=2E=6(n-2)

    4 .\sum_{i=1}^{n}A^{3}_{i,i}=6F=12(n-2)

    0번에서, 연결된 점은 1로, 아닌 점은 0으로 표시합니다.(한 점에서 다른 점으로 연결된 길은 최대 1개입니다.)

    1번에서, i번째 점과 j번째 점에 간선이 존재하므로 자명합니다.

    2번에서, 자기 자신으로 가는 경로가 없으므로 자명합니다.

    3번에서, A의 모든 요소의 합은 총 간선 수의 2배이고, A^2의 i행 i열 성분은 i번째 점과 연결된 점의 수를 나타내므로 이 식이 성립해야합니다.

    4번에서, A^3의 i행 i열 성분은 3개의 간선을 지나 다시 자신에게 돌아오는 수를 뜻합니다. 이렇게 돌아오는 경로 하나당 면 한 개가 존재하고, 한 간선당 2번씩 중복되므로 전체 면 수의 6배입니다.

     

     따라서 답은 위 조건을 만족하는 행렬 A의 개수입니다.  A^2A^3 대각합을 구해보려 했습니다. 그런데 여기부터 막히더군요. 선형대수학 고수분들을 기다립니다...

    댓글 작성하기 좋아요1 댓글수0