어느 수학경시대회에 참석한 참가자 중 일부는 서로 친구라 한다. 어떤 참가자 $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 중국 TST1 3번문제
$1,2,\ldots ,n$($n \ge 3$)의 번호가 적혀있는 작은 공들이 있다. 아래 서술한 색칠 방법을 써서 각각의 공을 빨강, 노랑, 파랑, 보라 네 가지 중의 하나를 칠한다: 먼저 $n$개의 공을 원 주 위에 임의로 배열한다. 시계방향 순서대로 임의의 연속 3개의 공에 대하여 그 번호가 $i$, $j$, $k$라 하자.
(1) 만일 $i \gt j \gt k$이면 $j$번 공에 빨강을 칠한다.
(2) 만일 $i \lt j \lt k$이면 $j$번 공에 노랑을 칠한다.
(3) 만일 $i \lt j$, $k \lt j$이면 $j$번 공에 파랑을 칠한다.
(4) 만일 $i \gt j$, $k \gt j$이면 $j$번 공에 보라를 칠한다.
$n$개의 공의 두 가지 염색방법이 다르다 함은 적어도 하나의 공이 두 가지 염색방법에서 다른 색을 가진다는 뜻이다. 서로 다른 색칠 방법의 수를 구하여라.
(2013년 3월 13일, 출처, 4시간 30분)