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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대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가지 색을 사용해서는 회로가 없는 색칠을 할 수 없는 도형을 찾아라.
 

댓글 51

  • tommy 2019.08.03 10:12:47 비밀댓글
    비밀댓글 입니다.
    댓글수2
    • 수학장 2019.08.03 10:16:41 비밀댓글
      비밀댓글 입니다.
    • tommy 2019.08.03 10:26:31 비밀댓글
      비밀댓글 입니다.
  • 김우현 기자 2019.08.03 10:15:01

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

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

    좋아요4 댓글수0
  • Simon 2019.08.03 10:44:30

    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 2019.08.03 10:51:50

    좋아요0 댓글수1
    • Undefined 2019.08.03 13:38:22

      좋아요0
  • E=mc^2 2019.08.03 11:04:33 비밀댓글
    비밀댓글 입니다.
    댓글수0
  • E=mc^2 2019.08.03 11:27:08 비밀댓글
    비밀댓글 입니다.
    댓글수0
  • 수학장 2019.08.03 12:45:08 비밀댓글
    비밀댓글 입니다.
    댓글수0
  • 벡터장 2019.08.03 12:53:32

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

    좋아요3 댓글수4
    • 마이구미 2019.08.03 13:07:17

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

      좋아요1
    • 벡터장 2019.08.03 13:12:55

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

      좋아요0
    • 벡터장 2019.08.03 13:19:00

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

      좋아요2
    • 마이구미 2019.08.03 15:45:04

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

      좋아요0
  • pi314159 2019.08.03 12:55:20 비밀댓글
    비밀댓글 입니다.
    댓글수0
  • 아인수타인 2019.08.03 13:10:28

    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 2019.08.03 13:14:39 비밀댓글
    비밀댓글 입니다.
    댓글수0
  • 아인수타인 2019.08.03 13:21:57

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

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

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

    좋아요0 댓글수0
  • 김우현 기자 2019.08.03 14:49:54

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

    참고해주세요!!

    좋아요0 댓글수0
  • POLYMATH 2019.08.03 14:50:06 비밀댓글
    비밀댓글 입니다.
    댓글수0
  • Pcy070731 2019.08.03 14:52:09

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

    좋아요2 댓글수0
  • Undefined 2019.08.03 14:55:47

    3. snub dodecahedron

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

    좋아요0 댓글수1
    • Undefined 2019.08.03 15:18:59

      좋아요0
  • Leesj 2019.08.03 14:56:11

    3번 정이십면체 되나요?

    좋아요0 댓글수1
    • POLYMATH 2019.08.04 12:19:41

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

      좋아요0
  • tommy 2019.08.03 14:57:49

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

    좋아요0 댓글수1
    • Undefined 2019.08.03 15:03:04

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

      좋아요0
  • Undefined 2019.08.03 14:58:52

    회로있어요

    좋아요0 댓글수5
    • streaming 2019.08.03 15:06:13

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

      좋아요2
    • Undefined 2019.08.03 15:25:35

      아닙니다

      좋아요0
    • 뉴턴의 사과 2019.08.03 22:19:35

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

      좋아요0
    • POLYMATH 2019.08.04 11:51:01

      파란색 지나야 되요

      좋아요0
    • 아인수타인 2019.08.05 02:35:51

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

      좋아요0
  • 누굴까요 2019.08.03 15:13:34 비밀댓글
    비밀댓글 입니다.
    댓글수0