$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분)
태그 보관물: 계수조합론
2009 제23회 한국수학올림피아드 고등부 5번문제
집합 $\{1,2,\ldots,12\}$에 대하여 다음 조건을 만족하는 일대일대응함수 $f:A\to A$의 개수를 구하여라.
조건: 모든 $i\in A$에 대하여 $f(i)-i$는 $3$의 정수배가 아니다.
(2009년 8월 23일 오후, 2시간 30분, 출처)
2007 제20회 한국수학올림피아드 최종시험 2번문제
아래 그림과 같은 모양으로 벽에 부착되어 있는 16개의 타일에 각각 0 또는 1을 적는다. 이때, 서로 한 변을 공유하면서 이웃하는 두 타 일에 적힌 수들의 곱이 항상 0이 되도록 적는 방법은 모두 몇 가지인가?
(2007년 3월 24일, 4시간 30분, 3문제, 출처)
2004 제17회 한국수학올림피아드 최종시험 4번문제
원주 위에 서로 다른 번호가 매겨진 $n$개의 점이 있다. 이 점 중 $k$개의 점을 택하는 방법 중에서, 택하여진 임의의 점으로부터 시계방향으로 가장 가까운, 택하여진 점 사이에는 반드시 $3$개 이상의 점이 놓이도록 택하는 방법의 수를 구하여라. 단 $n$과 $k$는 $2$ 이상의 정수이다.
(2004년 4월 11일, 4시간 30분, 3문제, 출처)
1999 제12회 한국수학올림피아드 최종시험 5번문제
$1$, $2$, $3$, $4$, $5$, $6$의 순열 중에서 서로 다른 두 항씩 자리를 바꾸는 조작을 $4$회 시행하여 $123456$을 복원할 수 있으며 $3$회 이하의 시행으로는 복원이 불가능한 순열 $a_1a_2a_3a_4a_5a_6$을 생각하자. 이러한 순열의 개수를 구하여라.
(1999년 4월 18일, 출처4시간 30분)