어느 수학경시대회에 참석한 참가자 중 일부는 서로 친구라 한다. 어떤 참가자 $A$가 $B$의 친구라면 $B$ 역시 $A$의 친구라 한다. 만일 $n(\ge 3)$명의 참가자 $A_1,A_2,\ldots,A_n$에서 모든 $1\le i\le n$에 대해 $A_i$가 $A_{i+1}$의 친구가 아니고 이 $n$명 중 다른 모든 참가자쌍은 서로 친구라 할때 이 $n$명을 약한 친구 모임이라 하자. (단, $A_{n+1}=A_1$.)
마침 다음 성질이 만족된다고 하자: 모든 참가자 $C$와 $C$를 포함하지 않는 약한 친구 모임 $\mathcal P$에 대해 $\mathcal P$에 속한 참가자 중 $C$의 친구가 아닌 사람은 많아야 한 명이다.
이때 이 경시대회의 모든 참가자를 세 방에 잘 배치하되 같은 방에 있는 참가자끼리는 서로 친구가 되도록 할 수 있음을 보여라.
(6월 30일, 4시간 30분, 출처, 출제:세르비아)
태그 보관물: 그래프
2013 이란 TST2 4번문제
어떤 그래프의 각 선에 실수가 다음 조건을 만족하도록 적혀있다: 임의의 꼭지점에서 출발하여 짝수개의 선을 지나 같은 꼭지점으로 되돌아오는 모든 경우에 대해 지났던 선에 적혀있는 수의 합은 정확히 0이다. (단 한 선을 여러번 지나는 경우 그 수도 여러 번 더한다.)
이때, 각 꼭지점에 적당한 실수를 적으면 각 선에 적힌 수가 그 선의 두 꼭지점에 적힌 수의 합이 되도록 할 수 있음을 보여라.
(2013년, 출처)
2012 Miklós Schweitzer 수학경시대회 10번문제
3차원 공간에 있는 매듭 $K$가 있다. (즉, $K$는 원에서 $\mathbb{R}^3$로 가는 미분가능한 단사함수이다.) 그리고 $D$를 이 매듭의 다이어그램이라 하자. (즉 $D$는 $K$를 적당한 평면에 projection시킨 것이다.) $D$의 여집합은 검은색으로 칠하고 $D$의 안쪽의 영역들은 체스판처럼 검은색과 흰색으로 칠하되 선을 공유하는 두 영역은 서로 다른 색이 되게 한다. 검은색 영역을 꼭지점으로 하고 두 검은색 영역이 서로 한 점에서 만날때 그 대응되는 두 꼭지점을 선으로 이은 그래프를 $\Gamma_B(D)$라 하자.
a) $\Gamma_B(D)$에 spanning tree가 많아야 3개 뿐인 다이어그램 $D$를 갖는 모든 매듭을 결정하라.
b) 모든 매듭 $K$와 다이어그램 $D$에 대해 $\Gamma_B(D)$의 spanning tree 수는 홀수개임을 보여라.
2012 Miklós Schweitzer 수학경시대회 3번문제
채색수(chromatic number)가 $k$인 그래프의 선을 2색으로 아무렇게나 칠하더라도 모든 선의 색이 같은 $k$개 꼭지점을 가진 수형도(tree)를 부분그래프로 찾을 수 있음을 보여라.
2012 Baltic Way 팀수학경시대회 8번문제
각 선에 방향이 지정되어 있는 어떤 그래프(유향그래프)가 있다. 이 그래프의 어느 꼭지점에서 출발하더라도 선의 방향을 따라 이동해면 지났던 꼭지점으로 되돌아올 수 없다고 한다. 한편 이 그래프의 선의 수가 99를 넘지 않는다고 할 때 이 그래프의 선을 빨강색 혹은 파랑색으로 잘 칠하여, 아래 성질을 만족하게 할 수 있음을 보여라.
한 꼭지점에서 출발해서 같은 색으로 칠해진 선만 이용해서 선의 방향을 따라 이동하면 많아야 9번밖에 이동할 수 없다.
2012 제26회 한국수학올림피아드 고등부 2번문제
어떤 모임에서 학생 $A_1$, $A_2$, $\ldots$, $A_n$이 서로 악수를 하였다. 학생 $A_i$가 악수한 횟수를 $d_i$($1\le i\le n$)이라 할 때, $d_1+d_2+\cdots+d_n>0$이다. 다음 조건을 모두 만족하는 $i$, $j$ ($1\le i<j\le n$)이 존재함을 보여라.
(1) 학생 $A_i$와 학생 $A_j$는 악수를 하였다.
(2) $\displaystyle \frac{(d_1+d_2+\cdots+d_n)^2}{n^2} \le d_i d_j$
(두 학생이 악수를 여러 번 할 수도 있다.)
(2012년 8월 19일 오전, 2시간 30분) (중등부 4번문제와 동일)