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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대10. 한 점에 모이게 그래프 색칠하기

2017.10.01

같이 풀어볼까?

네이버밴드 구글플러스

각각의 변이 방향을 가지고 있는 그래프를 ‘방향그래프(direct graph)’라고 부른다. 다음 두 조건을 만족하는 특수한 방향그래프 \large G를 생각하자.


(i) 각 꼭짓점에서 출발하는 변의 갯수가 항상 두 개이다.

(ii) 임의의 꼭짓점에서 다른 꼭짓점으로 가는 경로가 있다. (이러한 그래프를 ‘강연결’ 그래프라고 한다.)


아래 두 그림은 우리가 다룰 그래프들의 예이다. 한 꼭짓점에서 출발해서 다른 꼭짓점에 도착하는 변이 꼭 하나일 필요도 없고, 한 꼭짓점에서 출발한 변이 자기 자신으로 도착할 수도 있음을 주의하자.

 

 

두 가지 색깔, 흰 색(0)과 검은 색(1)을 사용해 다음 두 규칙을 만족하도록 변을 색칠하는 것을 좋은 색칠’이라 하자.
(a) 각 꼭짓점에서 출발하는 두 변에 칠해진 색은 서로 다르다.

(b) 다음 조건을 만족하는 2진수 수열 \large w=w_1 w_2 \cdots w_n 이 존재한다.

 

“각각의 꼭짓점에서, 수열의 색깔에 해당하는 변을 \large {\color{Blue} w_1}부터 \large {\color{Blue} w_n}까지 순차적으로 따라가면 항상 같은 꼭짓점에서 만난다.”


예를 들어 위 왼쪽 그래프는 위처럼 색을 칠하면 좋은 색칠이다. \large w=0 이면 어떠한 꼭짓점에서 0을 따라 가도 항상 꼭짓점은 \large J에서 끝남을 알 수 있다. \large w=10,01,11101,111011 등 0을 포함하는 수열이면 항상 조건 (b)를 만족함을 관찰해 보자.

 

질문 0(워밍업). 오른쪽 그래프에 주어진 색칠은 좋은 색칠이 아님을 보여라. 또한 꼭짓점 \large K에서 출발 하는 두 변의 색깔을 바꾸면 좋은 색칠이 됨을 보여라.


질문 1. \large G가 출발 꼭짓점과 도착 꼭짓점이 같은 변을 가진다고 하자. (위 두 그래프는 둘 다 이러한 변을 가진다.) 이 그래프는 좋은 색칠을 가짐을 보여라.


질문 2. \large G에 좋은 색칠이 있다고 하자. 그러면 (b)를 만족하면서 길이가 \large \frac{v^3}{2}보다 작은 수열을 찾을 수 있음을 보여라. 단, \large v는 그래프의 꼭짓점의 개수다.


질문 3. \large G에 좋은 색칠이 있다고 하자. 한 꼭짓점을 선택하고, 그 꼭짓점을 시작점과 끝점으로 하는 경로들을 모두 생각해 보자. 이때 이러한 길이들의 최대공약수는 1 이어야 함을 보여라.

(예: 왼쪽 그림에서 \large I를 선택하면, \large I \rightarrow J\rightarrow I,\, I \rightarrow J \rightarrow J \rightarrow I등의 경로를 생각할 수 있고, 이러한 길이의 집합은 2와 3을 포함하므로 최대공약수는 당연히 1이다.)


질문 4. 질문 3의 조건을 만족하는 그래프 \large G가 있다고 하자. 즉, 어떤 꼭짓점에서 출발하는 경로들을 모두 살펴보면 길이들의 최대공약수가 1이 된다고 하자. 이 그래프에는 좋은 색칠이 존재할까?
 

10월 20일 현재, 0, 1, 2, 3번 문제를 구머 선수가 해결했습니다^^. 주정훈 멘토에 따르면 4번 문제에 관해선 아직 좋은 아이디어가 없다고 합니다. 새로운 관점에서 문제를 풀어주세요!

댓글 71

  • 구머 2017.10.01 15:07:02

    질문 0: 오른쪽 그래프에 좋은 색칠이 되게 하는 W=w1w2...wn이 존재한다고 가정하자. 이때, wn이 0이라면 I,J,K에 대해 자기 꼭짓점에 도착하는 0으로 색칠된 변이 각각 1개밖에 없기 때문에, W1=w1w2...wn-1도 오른쪽 그래프가 좋은 색칠이 되게 하는 이진수 수열이다. wn이 1일때도 같은 방법으로 W=w1w2...wn-1가 되므로,  

                                                        'W=w1w2...wn이 좋은 색칠이 되게 하는 W라면 W1=w1w2...wn-1도 좋은 색칠이 된다'

    가 성립한다. 따라서 위 방법을 계속 반복하면 w1은 좋은 색칠이 되어야 하는데, w1이 1이나 0일때는 오른쪽 그림이 좋은 색칠이 되지 않음을 쉽게 알 수 있다. 여기서 모순이 발생하므로, 오른쪽 그래프는 좋은 색칠이 아니다!

     

    꼭짓점 K에서 출발하는 두면의 색깔을 바꾼 경우에는 w=100일때 잘 성립한다.

     

    모두 좋은 추석 보내세요!!

    좋아요3 댓글수1
    • 프로온 2017.10.05 01:26:02

      야~ 최고에요~

      좋아요0
  • 번즈상 2017.10.05 01:26:12

    질문 1: 그래프G 중에서 질문1에서 제시한 조건을 만족하는 무수히 많은 원소가 있는 집합을 g라고 하자. g에서 몇 개(1개이상)의 원소가 파란색으로 쓰여진 문장을 만족한다고 하자.

    그것은 즉 조건b를 만족하는 꼴이 되므로 좋은색칠이다.(그 원소=그래프) 그런데 그러한 그래프가 '됨'이 아닌 '가짐'을 언급했으므로 위의 제시된 그림 왼쪽에서 바로 참임을 알 수 있다.

    좋아요0 댓글수4
    • 프로온 2017.10.05 01:27:21

      저런! 저랑 생각이 동치시네요

      좋아요0
    • 구머 2017.10.05 10:40:13

      음..질문을 제대로 이해하지 못하신 듯 한데,(1)의 조건을 만족하는 그래프 전부가 b를 만족하도록 색칠할 수 있음을 보여야 합니다. (1)조건과 b를 만족하는 그래프가 존재하는 것을 보이는 것이 아닙니다.

      좋아요0
    • 번즈상 2017.10.05 18:01:30

      이런. 미리 변을 마련해놓고 '색칠'하는 것이었군요. 질문을 제가 잘못 이해했군요. 문제도 잘못 이해한듯 하네요. 지적해주셔서 감사합니다. 그리고 덧붙이면

      프로온님은 제 친구입니다. 동일인이 아님을 밝힙니다.

      좋아요0
    • 여백 패르마 2017.10.05 20:17:23

      친구셨네요...ㅎㅎ  동일인일 줄 알았습니다...

      좋아요0
  • 번즈상 2017.10.05 01:39:14

    질문2 에서 대체 길이가 뭡니까? 무슨 소리입니까!! n을 말하는 것입니까? 이런 방금전에 새 소식이 들어왔어요. 수열의 길이 라는것이 정의되어 있다는군요.

    좋아요1 댓글수1
    • 프로온 2017.10.05 01:40:18

      야~ 저는 제 추측에 의존중이었는데 님 댓글을 보고 논리의 근거가 세워졌어요. 정말 감사합니다~yes

      좋아요0
  • 여백 패르마 2017.10.05 14:55:42

    (4)번 푼듯.... 풀이는 나중에 쓰겠습니다.

    좋아요0 댓글수0
  • 여백 패르마 2017.10.05 16:03:28

    (4)번 증명

    수학적 귀납법을 써 봅시다.

    먼저, 점이 2개일때 명제가 참인지 보여야 합니다.  그리고 그림을 그려보면 그렇다는 것을 쉽게 알 수 있습니다.

    그 다음, 임의의 수개의 점을 가지고 있는 명제를 만족하는 그래프가 있으면 (임의의 수+1)개의 점이 있는 그래프도 성립함을 보여야 합니다.

      먼저, 임의의 수개의 점을 가지고 있는 그래프(명제를 만족함)에서 새로운 점 Dn이 더해지고 두개의 점이 점과 자기 자신을 두개의 점 a,b과 연결하면 좋은 색칠이라는 것을 증명합시다.

    증명 :임의의 수개의 그래프에서 되던 좋은 색칠의 wn에 다가 1 또는 0을 붙이면 Dn에서 시작하는 좋은 색칠이고, 그 곳부터 시작하지 않으면 전 그래프와 같아지니 증명됬습니다.

      그런데,임의의 수의 점을 가진 그래프 (페르마 그래프라고 부릅시다.)에서 Dn이 더해진 그래프가 달라젔다고 합시다.페르마 그래프에서 한개의 선이 Dn을 향해 진것입니다. 그때도 좋은 색칠이 됩니다. 단, 그 Dn이 준 선위에 있는 수가 a가 Dn에게 준 선위에 있는 수와 달라야 하고, 한 선을 Dn으로 부터 받은 점은 Dn으로 부터 선을 준 점이여야 합니다. 또, Dn이 준 2개의 점은 연결되어야 합니다.즉, 좋은 색칠이 가능합니다.(wn= 10 또는 01)

      2개가 줬다 해도 문제가 없습니다. 단 Dn이 화살표를 준 점이 돌려줘야 하고, 그 돌려줬을 때 한 쪽은 화살표에 있는 수가 달라야 하고, 한쪽은 같아야 됩니다. 또, Dn이 화살표를 준 점은 연결되야 합니다. 그러면 wn은 1(여러 연결된 선의 색칠을 이어 쓴 수열)0  또는 0(")1이 됩니다.즉, 좋은 색칠이 가능 합니다.

      3개 이상도 문제가 없습니다. 왜냐하면 3개 이상 주었을 때 새로 생긴 점이 주지 못한 점들은 쓸모가 없으니 2개 준 것과 같고, 그러면 됩니다.

    즉, 수학적 귀납법으로 (4)번은 참이 됩니다.   

    좋아요0 댓글수11
    • 여백 패르마 2017.10.05 16:17:15

      점에 기호를 붙인다니...  뭔말이지요?

      좋아요1
    • 구머 2017.10.05 16:28:04

      예를 들자면.. 새로운 점에는 Dn, Dn과 연결된 두 점 들을a,b..이런 식으로요. '점'이라는 말이 너무 많이 나와서 많이 헷갈립니다

       

      좋아요0
    • 여백 패르마 2017.10.05 16:48:22

      수정했습니다. 구머 님께 조언 해주셔서 감사하다는 말을 전해드리고 싶습니다.  다른 오류가 있으면 댓글로 알려주시면, 감사하겠습니다~^^

      좋아요0
    • 구머 2017.10.05 17:21:15

      모든 명제를 만족하는 그래프가 페르마 님이 제시한 조건들 중 하나를 포함해야 한다는것을 증명해야 합니다

       

      좋아요0
    • 여백 패르마 2017.10.05 17:39:47

      분명히 제가 말한 것들은 서로소입니다.(왜냐하면 전의 그래프가 길이가 2인 경로를 포험했으면 당연하고, 2의 배수를 포함해도 당연하며, 2와 서로소인 수가 길이인 경로를 포함하면 당연하기 때문입니다.)

      또, 이 증명은 모든 그래프에 관한 증명이니 맞는 것 같네요.....

      좋아요0
    • 구머 2017.10.05 20:33:17

      혹시 4에서 모든 그래프가 길이가 2인 수열을 가진다고 주장하고 싶으신가요?

      좋아요0
    • 여백 패르마 2017.10.05 22:14:58

      모두 그런것 이 아니라 제가 말한 그래프들은 모두 서로소라는 것입니다.

      좋아요0
    • 구머 2017.10.05 22:33:26

      풀이에 '한 선을 Dn으로 부터 받은 점은 Dn으로 부터 선을 준 점이여야 합니다'라 하셨는데, 그런 점이 없는 그래프의 경우도 있지 않나요..

      좋아요0
    • 여백 패르마 2017.10.06 13:28:16

      다시 보니 다시 돌려줄 필요가 없네요. Dn이 준 점과 받은 점이 연결만 되면 1(연결됬을 때의 경로의 색칠)0  또는 0(")1으로 하면 끝납니다.

      좋아요0
    • 여백 패르마 2017.10.06 22:17:43

      제가 언제나 그 두 점은 연결되어 있다는 것을 증명한 듯 합니다. 하지만 풀이는 내일쯤에 올릴 수 밖게 없습니다. ㅠㅠ

      좋아요0
    • 여백 패르마 2017.10.07 20:23:33

      두 점이 연결되는 경우의 수는 그래프가 m개의 점을 가질 때 2^m-m-1입니다. 또, 그래프의 선의 수는 2m개 입니다.수학적 귀납법을 씁시다. m이 4보다 크던가 같으면 성립한다는 것을요.(2^m-m-1>2m이라는 것말이죠.) 먼저, m=4일때 성립합니다. 또, 2^m-m-1>2m이 성립할 때 2^(m+1)-m-2>2m+2가 성립합니다. 즉, 수학적 귀납법과 비둘기의 집의 원리에 의해 언제나 연결 가능합니다.

      좋아요0
  • 구머 2017.10.05 17:26:01

    일단 반쪽짜리 1번, 문제 푸는데 큰 쓸모는 없어보이지만 일단 올려봅니다.

    어떤 두 점 a,b가 있고, a에서 b로, b에서 a로 가는 변이 있다고 합시다.(문제조건에 의해 그런 a,b는 있습니다) 이제 어떤 점 c에 대해, c에서 b로 가는 가장 짧은 경로의 길이를 n이라 하면, c가 n층에 있다고 합시다. (a는 1층에 있습니다)

    Lemma) n층의 모든 원소는 n-1층으로 가는 변이 적어도 하나가 있다.

    증명: n층의 원소 c에서 b로 가는 가장 짧은 경로를 c->d->......b라고 하면, 이 경로의 길이는 n이고, 따라서 d에서 b로 가는 경로의 길이는 n-1이므로 d는 n-1층에 있다.

    이제 a와 b를 잇는 변을 1로 색칠하자. 그리고 n층에서 n-1층으로 가는 변도 1로 색칠한다. 그럼 wn을 111111111. . 11로 하면 모든 점들은 a와 b로 모이게 된다. 이제 0을 계속 반복하다 보면 a와 b에 있었던 점들이 어떤 층에 가게 될 것인데, 만약2개의 점 각각이 있는 층의 차가 2의 배수가 되면, 그때 1을 계속 돌리면 결국 a와 b중 한점에서 만나게 된다. 그러나 0을 계속 돌려도 층의 차가 2의 배수가 되지 않는 그래프가 존재하는데, 이러한 그래프들은 따로 생각해서 한 점에서 만나게 하는 알고리즘을 새로 만들어내야 한다.(아직 거기까진 생각 안 해봤습니다..)

    좋아요0 댓글수1
    • 구머 2017.10.06 07:19:57

      아차... 제가 문제를 오해했군요. 저는 점a ,b가 있어서 a에서 b로, b에서 a로가는 변이 있다는 조건인 줄 알았습니다.

      그럼 풀이를 재작성해봅시다.

      문제조건을 만족하는 점을 a라 두고, 앞과 동일하게 임의의 점 c에서 a로 가는 가장 짧은 경로의 길이를 m이라 가정하면, c가 m층에 있다고 하자. 이때 m층의 모든 점들은 m-1층으로 가는 변을 적어도 하나는 가진다.(앞부분에서 증명참조) 이제 m층에서 m-1층으로 가는 모든 경로를 1로 색칠하자. 단, m층의 어느 점이 m-1층의 두 점으로 가는 특수한 경우가 생길 수도 있는데, 그런 경우엔 하나의 변에만 1을 칠하면 된다. 

      또, 어떤 그래프에서 임의의 점들을 뽑았을 때, 그 점들이 위치한 층의 최댓값이 n이면 그 점 상태를 n층 아파트라고 하자. 이때 a는 0층에 있다.

      이제 위 조건을 만족하는 (색칠된)그래프가 좋은 색칠임을 보이자. 먼저 위 그래프는 각 점마다 정확히 1개의 1을 발사(?)한다. 왜냐하면, a는 자기 자신에게 1을 주고, 모든 점들은 0층에서 n층 중 하나에 포함되있으며, 모든 점이 자기가 속한 층의 바로 아래층에 1을 줄것이기 때문이다. 또, wn=111...11을 하면, 1을 한 번 시행할 때마다 n층 아파트는 n-1층 아파트가 되고, 이 과정을 무한반복하면 결국 0층 아파트가 되는데, 0층에는 a밖에 존재하지 않는다. 따라서 모든 점에 a가 모였고, 위 그래프는 좋은 색칠이다

       

       

      좋아요0
  • 번즈상 2017.10.05 23:40:53

    질문1에 대한 증명 앞부분 : 수열 1111111..11을 보니까 제생각이랑 살짝 비슷한 느낌이 듭니다. 저는 뺑뺑이도는 변이 있는 점을 'A'라고 하고 그점에 모인다고 했습니다. 만약 뺑뺑이 도는 변의 색깔을 0이라고 한다면 A에 모이고 나서 계속해서 000000...00이 이어진다면 한번이라도 A에 오면 한점(A)에 다 모일것입니다. 특수한 상황이지만 점A를 제외하고는 구머님의 '층'아이디어 처럼 일방향으로 간다고 하고 그변의 색깔이 0이라고 했습니다. 시점의 차이가 분명히 나겠지만 (순서) 분명 A에 다 모일것입니다. 그리고 점A가 여러 개 있을 때를 생각해 보았습니다. 즉 뺑뺑이 도는놈이 두점 있는 거죠. 뺑뺑이 도는 변의 색깔은 각각 같을 수도 있고 다를 수도 있죠. (여담이지만 '동조'와 비슷하다는 생각이 스치네요) 만약 A1에 뺑뺑이 도는 변의 색깔이 또다시 0이라고 하고 다른 점에서 뺑뺑이 도는 변의 색깔은 전부 다 1이라고 합시다. 점이 여러 개가 있으면 그점들을 무작위로 배열할 수도 있지만 일단 7명 모여! 할때처럼 각각의 점들은 0인 색깔의 변만 순서대로 연결되어 있다고 합시다. 색깔은 변을 그리고 나서 임의로 부여한다고 생각을 한거니까요. 한점만 뺑뺑이 도는변이 0이고 다른 점이(만약에 여러개라면) 뺑뺑이 도는 변의 색깔이 1이라면 수열이 W=0000000000....000000000 이라고 했을때 무작위로 배열된 변들 속에서 0인 색깔의 변은 정돈돼 있을 수 있습니다. 색깔이 1인 변에 대해서 언급하면 한점 빼고는 뺑뺑이 도는 변이 색깔이 1이고, 뺑뺑이 도는 변이 없는 변들은 0과 1이 어딘가로 갈텐데, 점들을 연결시킨 것에 1로 색칠된 변만 적당히 탄력성을 부여해서 늘어나게 해주면 0으로 색칠된 변으로 연결된 점들의 집합(원 모양?) 이 나옵니다. 즉 어느 방향으로 가도 수열이 00000000...0000이면 결국에는 A1에 모일수 밖에 없게 되는 것이죠. 유일한 예외가 A1입니다(다른 뺑뺑이 도는 변이 있는 점들은 모두 뺑뺑이 도는 변의 색깔이 1이고, 다른 점으로 가는 변의 색깔이 0인데 이것은 그 반대이다.) 두서없어서 죄송합니다.

    좋아요0 댓글수4
    • 번즈상 2017.10.05 23:50:13

      이런 약간의 혼동이 생겨서 다시 댓글을 답니다. 0인 색깔의 변이, 뻗어나가는 변에 한해서 생각할 때, 갔던 곳에서 다시 지나 갔던 곳으로 뒤돌아오지 않도록 하는 변의 색깔을 모두 0으로 정합시다. 그러한 것은 어떠한 선의 배열에도 가능할 것입니다. 왜냐하면 모든 점들은 연결되 있기 때문입니다. 왜 그런가 하면 분명히 모든 점이 다른 점으로 뻗어 나갑니다. 만약 어떠한 점에 여러점에서 뻗친 선이 있다고 할지라도 그 경우에도 가능할 것입니다. 극단적으로 모든 점이 뺑뺑이 도는 변이 있다고 합시다. 그렇다고 하더라도 분명 모든점은 연결될 수 있습니다. 위에서 말한 원모양은 나올수 없다 할지라도 가능할 것입니다. 머릿속 그림을 말로 나타내니 굉장히 길어졌군요. 

      좋아요0
    • 번즈상 2017.10.06 00:07:38

      저것에 대한 명확한 설명은 A1으로 뻗어나가는 변이 있는 점의 개수와 연관이 있습니다. 점이 총 N개라고 하면 직접적으로 A1과 만나는 점은 1개에서 N-1개 사이입니다. 그런데 모든점들은 다른점으로 뻗어나가므로 분명 변들의 방향성은 제외한 채로 점들은 연결이 되어있습니다. 직접적으로 A1과 만나는 점들은 다 다른 경로의 종점에 다다르기 직전의 점으로 치부하고 생각해 봣을때 분명 모든 점들은 얽혀 있지만(복잡해서 상상이 안되는 그래프가 특히) 방향성을 부여하고 나서 지나왔던 점으로 다시 되돌아 오지 않게 색깔을 부여할 수 있습니다. 그 색깔을 A1의 뺑뺑이도는 변의 색깔과 똑같이 하고 만약에 A1이 아닌 다른 뺑뺑이 도는 변을 가진 점에게는 도는 변에게 다른 색깔을 부여하고 나서, 다른 색깔이 1이라면 수열이 0000000...00000000000....이라면 분명히 A1에서 다 만날것입니다.

      좋아요0
    • 구머 2017.10.06 07:22:15

      혹시나 해서 말해드리겠습니다. 1의 그래프는 '변'만 주어져 있지, 색칠한 상태가 아닙니다

       

      좋아요0
    • 번즈상 2017.10.06 13:03:04

      맞습니다. 변만 주어져있지 색칠은 나중에 하는거니까요

      좋아요0
  • 구머 2017.10.06 23:19:53

    2번. 아직 다 풀지는 않았지만 이 방법대로 밀면 풀릴 것 같아서 공유해봅니다.

    먼저 G가 좋은 색칠이므로, G의 점들 중 2개를 골랐을 때, 그 두 점이 한 점에 만나게 하는 경로가 존재합니다. 이때, 이 경로의 길이가 v(v+1)/2 이하라고 가정합시다.(가정일 뿐 아직 증명되지는 않았습니다) 그러면 v개의 점들에서 2개의 점을 하나로 모으고, 그 모은 점을 또다른 점과 모으고... 이 과정을 반복하면 한 점에 모이게 되는데, 모으는 과정은 아무리 커도 v-1번이면 충분하기 때문에 v(v+1)(v-1)/2번 안에 모든 점을 한 점에 모을 수 있습니다.

     

    위 증명의 가정은 이제 증명할 대상입니다. 그런데 아마 되지 않을까 싶네요ㅋㅋ 

    좋아요0 댓글수0
  • 여백 패르마 2017.10.07 22:21:23

    10(4)증명

    수학적 귀납법을 이용하자.

     먼저, 2개의 점이 있을 때 가능하다는 것을 증명해야 한다. 그림을 그려보면 맞다는 것을 알 수 있다.

     그 다음으로는 n개의 점을 가지고 있는 그래프가 성립할때 n+1개의 점을 가지고 있는 그래프도 성립한다는 것을 증명해야 한다.

    n개의 점이 있는 그래프에 그냥 새로운 점이 있어서 연결하는 것은 당연히 좋은 색칠이 가능 하다고 할 수 있다.

    또, 한점이 선을 때어서  새로운  점에게 준것도 문제 없다.wn=1(새로운 점이 받은 선을 준 점과 새로운 점이 준 점과 연결의 경로의 색칠)0 또는 0(")1으로 하면 된다.(나의 전 덧글을 보면 언제나 연결 되어있다는 것을 증명한 것이 있다.)

     두점이 때어 준것도 문제가 없다. wn=(Dn~a 또는 Dn~b의 색깔 (Dn=새로운 점, a,b는 새로운 점이 받은 선을 준 점))(Dn이 준 점중 하나와 a,b의 경로의 색깔 )(a~Dn의 경로의 색깔 또는 b~Dn의 경로의 색깔)이면 끝난다. 또, 언제나 이어지니 가능하다.

    3개이상 이어질때는 2개 빼고는 쓸모가 없으니 된다.(2개가 이어진것과 같아지기 때문이다.)

    Q.E.D

    좋아요0 댓글수5
    • 여백 패르마 2017.10.07 22:30:20

      꺅~~ 헐 그런데 새로운 점은 뭔가요....

      좋아요0
    • 구머 2017.10.07 22:35:22

      게다가 좋은 색칠도 가능하군요

      좋아요0
    • 여백 패르마 2017.10.08 20:37:43

      그리고요, 전의 그래프와 지금의 그래프와 다른데요?....

      좋아요0
    • 구머 2017.10.08 21:42:17

      위에 껀 그냥 무시해주시면 좋을 것 같고 Dn이 새로운 점입니다. (잘 안보일수도 있음)

      좋아요0
    • 구머 2017.10.08 22:12:01

      좀 더 좋은 반례가 있군요.  이번엔 위 점들 중 어떤 점을 새로운 점으로 잡아도 패르마님이 제시한 조건이 성립하지 않습니다.

      좋아요0
  • 구머 2017.10.07 23:42:59

    3번: 그래프 G의 어느 점 D를 생각하자. 이때, D를 출발점으로 하는 변의 도착지점을 E라고 하면, G는 좋은 색칠이기 때문에 D와 E가 한 점에 만나게 하는 경로가 존재한다. 만약 D와 E가 G의 임의의 점 F에서 만났다 가정하면, F에서 D로 가는 경로 또한 존재하므로 D와 E는 어떤 경로(---a)에 의해 D로 모일 수 있다. 이제 a의 길이를 n이라고 하자. 이때, D에서 시작해서 끝나는 경로는 a가 있고, D에서 E로 간후 a를 시행하는 경로가 있으므로 경로의 길이에는 n, n+1이 있다. 즉, 임의의 점 D에 대해 D에서 시작해서 끝나는 모든 경로의 길이들의 최소공약수는 1이다.

    좋아요0 댓글수2
    • 번즈상 2017.10.11 02:17:58

      D에서 F로 갈때의 길이(E를거치지않을때)와 E에서 F로 갈때의 길이가 같다는 전제가 깔려있는 것이죠? 그것은 자명하네요. 처음에 약간 이해가 안됐었습니다만, 부연설명을 하자면 D와 E가 F에서 만난다면 '동시'에 F에 있는 것이므로 얼마가 특정점(모든점)에서 중복되었든 간에 길이는 같죠. 그리고 F에서 D로 가는 길이는 애초에 공통변 같은 느낌이니 이것도 같죠. 또한 D와 E는 일반적인 점이므로 다른 점에서 출발했다고 하더라도 중간지점에도 저것을 적용할 수 있겠죠.

       

      좋아요0
    • 구머 2017.10.11 17:30:32

      처음에 D에서 F로 갈때 E를 거쳐도 별로 상관없습니다~

      좋아요0
  • 구머 2017.10.10 17:16:42

    2번: 우선 편의상 v개의 점에 1,2,....,v로 번호를 매기자. G에 좋은 색칠이 있으므로, 어떤 두 점을 골라도 그 두 점이 만날 수 있는 경로가 존재한다. 그 경로를 w라고 하고, w가 진행될 때마다 각각의 단계에 두 점이 위치한 곳을 나타낸 수열을 w2라고 하자. 이때, w2는 (a,b)->(a1,b1)->...이런 식으로 나타난다. 이제 이러한 경로들 중 가장 짧은 경로를 W2라고 두자. 

     

    Lemma) W2에는 구성 성분이 같은 원소가 없다.(즉, 예를 들어서 W2에 (1,2)가 존재한다면, 그 (1,2) 이외의 다른 (1,2)와 (2,1)은 존재하지 않는다)

    증명: (수학적 귀류법) 만약 W2에 구성 성분이 같은 원소가 있다고 가정하자. WLOG (1,2)와 (2,1)이 존재하고, (1,2)가 (2,1)보다 앞에 있다고 하자. 이때, W2를 (a,b)->(a1,b1)...(an,bn)->(1,2)->(an+2,bn+2)->...(am,bm)->(2,1)->(am+2,bm+2).....->(t,t) 라고 둘수 있다. 단, (t,t)는 두 점이 만났음을 의미한다. 이때, 새로운 수열 W3=(a,b)->(an,bn)->(am+2,bm+2)->(t,t)가 존재하는데, W3은 W2보다 짧으므로 W2가 가장 짧다는 가정에 모순이다.

     

    따라서 W2는 아무리 구성 원소가 많아도 vC2 +1을 넘을 수 없고, 즉 W2의 최대 길이는 \frac{v(v+1))}{2}+1를 넘을 수 없다. 또, 위 과정에서 (t,t)의 전 과정의 두 점을 모으는데 시행을 1번하고, 남은 v-1개의 점을 한 점으로 모으려면 두 점을 한점으로 모으는 과정을 최대 v-2번만 하면 되고, 즉 시행을 (v^2+v+2)(v-2)/2 +1번만 하면 v개의 점을 1개로 모을수 있는데, 위 시행이 (v^3)/2보다 작은 것은 수식 전개를 통해 잘 알 수 있다.

    좋아요1 댓글수5
    • 번즈상 2017.10.10 22:43:00

      따라서 ~~다음부터가 이해가 안되네요. 부연설명 해주실수 있으십니까? 또 an bn 에서 am+2 bm+2로 가는것도 이해가 안되네요.  또 (1,2)가 한번더 있다면  그것의 논증은 알겠지만 (2,1)은 잘 모르겠네요. 사려깊음에 감사를 표합니다.

      좋아요0
    • 구머 2017.10.11 00:21:57

      학원 가야 해서 확실히 안한 부분이 있는데 지금 올릴게요. 먼저 논란의 여지를 없애기 위해 순서쌍을 오름차순으로 배열합시다.(예를 들자면, (2,1)은 (1,2)로) 또, 원래 W2에서 (1,2) 순서쌍이 각각 n+1번째, m+1번째에 있다고 합시다. WLOG n<m입니다. 이때, W2에는 두 개의 (1,2) 사이에 다른 경로가 있었는데, 새로운 수열 W3에서는 그 다른 경로를 제거한 것입니다. 이때, W3을 시행하여도 (a,b)에 있던 두 점이 한 점에 만나게 되고, W3은 분명 W2보다 길이가 짧습니다. 이것은 위 설명대로 W2가 가장 짧은 경로(a와 b를 연결하는)라는 조건에 모순이므로, 따라서 W2에는 같은 순서쌍이 없습니다. 그런데 순서쌍의 전체 개수는 vC2입니다. 즉, W2는 아무리 많아도 vC2+1개의 원소만을 가진다는 것이죠.(여기서 뒤에 +1한 것은 마지막 (t,t)때문에 한 것입니다) 만약 W2가 vC2+1보다 크다면, 비둘기집의 원리에 의해 같은 순서쌍이 2개 생길 것이고, 이는 Lemma)에 의해 모순입니다. 따라서 '모든 두 점은 vC2의 시행 안으로 한 점에 만나게 할 수 있다' 라는 것이 증명되었습니다.//(부연: '시행'을 하는 것은 순서쌍과 순서쌍 사이의 화살표를 따라가는 것과 같습니다. 따라서 vC2+1개의 순서쌍이 있으므로 시행은 vC2번만 하면 됩니다)

      이제 v개의 점을 하나로 모아봅시다. v개의 점들 중 2개를 골라서 vC2번 안에 그 두 점을 한 점으로 모읍시다. 그리고 그 모아진 점과 또 다른 점을 모읍니다. 이런 과정을 최대 v-1번만 하면 v개의 점은 하나로 모아집니다. 즉, (v-1)vC2 안에 v개의 점을 하나로 모을 수 있습니다. 그런데 vC2은  \frac{v(v-1))}{2}이라는 것은 잘 알려져 있고, 즉 (v-1)(v-1)v/2번 안에 v개의 점을 하나로 모을 수 있다. 그리고, (v-1)(v-1)v/2는 \large \frac{v^3}{2}보다 작으므로,  \large \frac{v^3}{2}의 시행 안에 v개의 점을 하나로 모을 수 있다. Q.E.D

      좋아요0
    • 구머 2017.10.11 00:32:12

      위쪽에 오타 있습니다~ vC2가 v(v+1)/2가 아니라 v(v-1)/2입니다! 따라서 ~~부터는 두번째 댓글의 풀이를 참조하시길 바랍니다. 그리고 번즈상님이 (1,2)에 대한 논증은 알겠지만 (2,1)에 대한 논증은 잘 모르겠다고 하셨는데, 지금 제가 고려하고 있는 것은 단지 두 점의 위치일 뿐, 그 두점이 원래 a점에 있었는지 b점에 있었는지는 크게 중요하지 않습니다. 따라서 (1,2)나 (2,1)이나 점의 위치는 똑같으므로 같은 논증을 하시면 됩니다. 그리고 부연풀이에서 언급했듯이, an bn에서 am+2 bm+2로 간 이유는 중간의 (1,2)->...->(1,2)과정에서 (1,2)로 다시 돌아오는 것보다는 다시 돌아오는 과정을 거치지 않고 바로 an bn->(1,2)->am+2 bm+2로 넘어가는 것이 더 빠르기 때문에 중간 과정을 생략한 것이기 때문입니다

      좋아요0
    • 번즈상 2017.10.11 01:49:53

      최대 v-1회 시행(두점을 하나로 모으는 시행) 한다는 말은 그것보다 더 적을수도 있다는 말인데 (t,t) 와 다른 임의의 점을 모으는 겁니까? 아니면 아무거나 두점을 잡는다는 겁니까? 제 생각에는 앞의 말인거 같은데 앞의 말이라고 하면 // 중간에 지나가는 지점의 순서쌍이 만약 시작점이 된다면 굳이 한번더 시행하지 않아도 한점으로 모이는 것이므로 저렇게 '최대'의 표현이 된것이죠? 제가 제대로 이해했는지 모르겠네요. 그리고 저도 뭔말인지 몰랐는데요, WLOG는 '일반성을 잃지 않는 조건을 가지고 있는' 이라는 뜻이라고 하네요. 요즘 인터넷 좋습니다.

      좋아요0
    • 구머 2017.10.11 17:26:38

      먼저 앞의 말이 맞고요, 최대의 표현을 쓴 이유는 그런 이유도 있고 '우연히' 어떤 다른 두점이 하나로 모이는 운 좋은 상황도 발생할 수 있기 때문입니다. 하지만 최악의 상황을, 즉 우연히 어떤 두점이 하나로 모아지는 것이 없는 상황을 고려하여서 v-1번 안에 가능하다 라고 했습니다.

      좋아요0
  • 여백 패르마 2017.10.11 19:36:09

    사이클이 0개라면 모순입니다.

    이제 사이클이 1개라고 합시다. 그때는 서로소이고,언제나 가능합니다. 증명: 길이가 n보다 작다고 합시다. 그러면 사이클과 연결된 선들과 사이클의 개수의 합이 n일 때까지 합니다.(하나는 나가는 것, 하나는 오는 것) 그리고 그 전체를 같은 색으로 칠하면 됩니다.사이클의 길이가 정확히 n이면 그 사이클을 모두 같은 색으로 칠하면 됩니다. 또,n보다 넘으면 몇개는 자신에게 돌아오는 것이 있다는 것이니 그것들을 빼면 길이가 n인 것이 되니 끝납니다.

    그러니까 사이클이 여러개일 때를 알아야합니다.그리고, 2개일 때를 생각해봅시다. 사이클 2개가 연결이 없을 때, 제가 위에서 말한 조건을 생각하면 됩니다. 연결됬다고 합시다. 길이가 x인 사이클이 있고, 길이가 x+a인 사이클이 있다고 하자. 그러면 2x+a인 사이클이 있다.그것이 n-y라고 하자. 그러면 n>3y이면 좋은 색칠이 가능하다. 즉, n<3n일 때를 생갓해야 한다. 또, 모든 y에 대해 가능하니, 된다. 또, 2x+a인 것이 n이면 좋은 색칠이 가능하다. 또, n보다 크면 자기 자신에게 돌아오는 것이 있우니 그것을 빼면 된다.(x+a와 x가 서로소가 아닐때는 않된다는 것은 구머님이 증명하신 3번을 이용하면 됩니다. 3번의 대우는 '서로소가 아니면 좋은 색칠이 않된다"라는것이기 때문에 3번이 참이니 서로소가 아니면 않됩니다.)(구머님이 맞으시길 기원합니다....)

    3개이상일 때도 이런 방식으로 하면 가능 하기 때문에 된다.

    좋아요0 댓글수7
    • 구머 2017.10.11 21:30:13

      아마 4번을 말하는 것일 거고... '사이클'이 무엇인지 정의해 줄 수 있나요? 그리고 사이클과 연결된 선들과 사이클의 개수의 합이 n일때까지 뭘 하는 거죠? 그리고 저기서 사이클의 개수가 1개라고 했으니, 사이클과 연결된 선들의 개수가 n-1개일 때까지 무언가를 하는 건가요? 그리고 무엇을 하는지는 잘 모르겠지만, 사이클의 개수의 합이 n이 될 수 있다는 것도 증명해야 하지 않습니까?

      좋아요0
    • 여백 패르마 2017.10.15 11:04:28

      사이클은 자기 자신에게 돌아오는 경로를 말하는 것인데요....그리고 n이 된다는 것을 증명할 필요 없습니다.  또, 서이클이 여러개일때 를 생각하고 있습니다.

      좋아요0
    • 여백 패르마 2017.10.15 11:19:14

      수정 성공!

      좋아요0
    • 구머 2017.10.15 23:33:02

      제가 이해도가 나쁜 탓인가...풀이 이해가 잘 안되는군요. 그리고 사이클이 1개 또는 2개밖에 없는 그래프는 없지 않나요?

      좋아요0
    • 여백 패르마 2017.10.17 14:44:48

      또는 제 논술력이 별로일 수도 있습니다.(참고: 저 초딩 4라서 구머님이 이해하기 힘든것이 당연할지도...)

      그리고 사이클이 1,2개만 있는 그래프는 당연이 있지 않나요?

      좋아요0
    • 구머 2017.10.17 17:12:28

      예시를 들어주시면 이해하기 편할 것 같아요!(풀이에 관한 거요)

      좋아요0
    • 여백 패르마 2017.10.20 14:37:41

      엇! 오류 발견! 발견! 곧 고치겠습니다.

      좋아요0
  • 여백 패르마 2017.10.20 14:55:29

    자연수 집합의 원소인 수 k개만큼 사이클이 존재한다고 하자. 그러면 서로소가 아닌 것 들을 재외한 모든 그래프들은 가능하다.

    proof) r(자연수인 것)개만큼 겹친다고 하자. 그러면 사이클들의 길이는 a1,a2,a3,......,ar-1,a1+a2+a3+......+ar-1가 된다.

    사이클의 길이중 가장 긴 것의 길이가 n개 보다 작다고 하자.(n=그래프의 점의 개수.) 즉, 가장 긴 것의 길이는 n-y라고 하자.  n-y에서 나오는 것과 y에서 가장 긴 사이클로 가는 것들오는 것(그 가장 긴 사이클에서 나오는 것과 나머지 점들에서 나오는 것)들의 합이 y가 되도록 하면 된다. (절대로 한점에서 여러개가 되면 않된다. 릴레이여야 한다.) 

    그러면 긴것중 가장 긴것의 길이=n이라고 하자. 그러면 당연이 가능하다.

    긴 것중 가장 긴것의 길이가 n보다 길다면 다시 돌아오는 것이 있다고 하자. 그러면 자기에게 돌아오는 것이 있기 때문에 그것을 빼면 된다.

    3번의 대우는 '서로소가 아니면 좋은 색칠이 불가능 하다' 가 되기 때문에 서로소가 아닌 것은 뺀다. 

    Q.E.D 

    좋아요0 댓글수3
    • 여백 패르마 2017.10.24 14:48:45

      이해가 않되신다면... 수정 시도해보겟습니다.

      좋아요0
    • 여백 패르마 2017.10.24 14:57:00

      수정 성공!

      좋아요0
    • 구머 2017.10.24 16:51:20

      음..잘 이해가 안되네요 그런데 살짝 이상한 부분이 있는데, '서로소'라는 조건을 어떻게 사용하셨는지요?

      좋아요0
  • 여백 패르마 2017.10.20 22:18:24

    짝짝짝 구머 형님 0123다 풀으셨네요....

    좋아요0 댓글수0
  • 여백 패르마 2017.10.22 21:48:54

    그냥 생각한것인데, 서로소인 그래프의 집합과 좋은 그래프들의 집합은 일대응 대응이 아닌가요?   기수가 같잖아요...

    좋아요0 댓글수0
  • 구머 2017.10.22 23:51:16

    질문 4에서 '어떤 점에서 출발하는 모든 경로의 최대공약수가 1이 되어야 한다'라는 조건이 '그런 점이 존재한다'라고 받아들여야 하나요 아니면 '모든 점에 대해서 최대공약수가 1이 되어야 한다'가 되어야 하나요? 

    좋아요0 댓글수2
    • 여백 패르마 2017.10.23 15:52:51

      분명히 2개가 서로소이면 다른 것도 서로소입니다....

      좋아요0
    • 구머 2017.10.23 17:43:11

      아 생각해보니 어떻게 받아들여도 동치네요.

      좋아요0
  • 여백 패르마 2017.10.28 22:31:17

    저는 구머님의 아이디어 나쁜 그래프의 성질에 관심을 가졌습니다. 

    자신에게 (한점에서) 돌아오는 것이 2개이면 절대로 않됩니다. 그것이 좋은 색칠이 않되려면 같은 것이 있어야 한다. 그러면  않됩니다. 그 이유는 연결되면 하나더 생기고,  계속 연결되면 무한히 만들어 지기 때문에 말이 않된다. 또, 연결이 않되면 갈라진다. 계속 연결이 않되면 점으로 가는 뎨, 그것은 그래프가 아에 아니다. 중간에 연결되다가 않되면 원상태로 가고, 갈라졌다는 것과 모순이다. 즉, 않됨. 

    자신에게 돌아오는 것이 1개이여도 위 과정을 거치면 않된다는 것을 알 수 있다. 

    즉, 한점의 사이클이 있다면 길이가 1차이 날 수 없다.

    그렇기 때문에 한 점의 사이클의 길이중 짝수가 반을 넘으면 자신과 1차이나는 홀수들을 모두 지워서 짝수만 남고, 그러면 2로 모두 나눠 떨어진다.

    반을 않넘으면...... 모릅니다. (저 말이에요.)

    좋아요0 댓글수2
    • 구머 2017.10.28 23:09:31

      음..그 아이디어로 파려다가 답이 안 나와서 접었는데.. 그걸로 시도해보는 분이 계셨네요 저도 다시 한번 그방향으로 해볼께요!

      좋아요0
    • 여백 패르마 2017.10.29 20:51:32

      또 또 또 또 오류오류오류오류

      좋아요0
  • 여백 패르마 2017.10.29 20:51:04

    저는 전의 아이디어와 나쁜 그래프의 성질에 대한 구머님의 아이디어를 섞어 봤습니다. 

    수학적 귀납법을 이용해 보았습니다. 

    점이 두개일 때는 당연히 된다는 것을 알 수 있습니다.   

    점이 임의의 수개일 때 그 수보다 점이 하나 더 많을 때도 참이라는 것을 증명 합시다. 먼저, 새로생긴 점( 패르마 점) 이 생기면서 아무 다른 점들이 그 패르마 점에게 준 것이 없다면 자명하지요. 

    한 점이 주었다고 합시다. 그리고 그 패르마 점에게 준 점을 구머 점( 구머님~ 구머님 이름을 이용해봤습니다^^) 이라고 합시다. 그  패르마 점이 준 점을 여백 점이라고 합시다. 그러면 그 여백 점과 구머점은 연결 되어 있습니다. (1가지로) 또, 구머점은 임의의 소수 p의 배수가 길이인 사이클 2개을 가지고 있습니다. 즉, 그 여백 점과 구머점이 페르마 점을 가지 않고 연결 되어 있다면 (여백점부터 구머점), 그리고 그 길이가 p로 나눴을 때 p-2일때 가능케 됩니다. (p-2가 언제나 가능하다는 것을 증명하지 못했습니다.) 또, 2개가 줬다고 하면, 즉 구머점이 2개라면 구머 점이 1개인 것과 똑같기 때문에 끝납니다. 또, 3개 이상(구머점이)이라면 2개의 구머점이 있는 것 같은것이기 때문에 됩니다. 

    즉, p-2로 언제나 가능하다는 것을 증명하면 됩니다. 

    좋아요0 댓글수5
    • 여백 패르마 2017.10.30 18:14:23

      언제나 p-2가 가능하다는 것을 증명할 수 있으신 분과 논리상 문제를 찾으신 분은 댓글 달이주시기 바랍니다

      좋아요0
    • 구머 2017.10.30 18:49:02

      제가...언제...제 이름 마음대로 쓰라 했죠..?(ㅋㅋ농담입니다 마음대로 쓰세요)

      좋아요1
    • 여백 패르마 2017.10.30 19:19:58

       안 된다고요!!!!!!!!! 뜨헉  crying

      ( 이것도 농담....  cheeky )

      좋아요0
    • 여백 패르마 2017.11.19 19:51:00

      p-2가 언제나 가능한다는 근거를 아시겠는 분 좀 대덧글 올려주시길 바랍니다.

      좋아요0
    • 여백 패르마 2017.11.20 14:25:14

      오류 찾으신 분도 환영

      좋아요0