1996 미국수학올림피아드 4번문제

0과 1만으로 된 $n$항의 수열 $(x_1, x_2, \dots, x_n)$을 길이 $n$의 이진수열이라고 부르자. 길이 $n$의 이진수열 중에서 연속한 세 항이 차례로 0, 1, 0인 경우가 없는 수열의 개수를 $a_n$이라 하고, 길이 $n$의 이진수열 중에서 연속한 네 항이 차례로 0, 0, 1, 1이거나 1, 1, 0, 0인 경우가 없는 수열의 개수를 $b_n$이라 하자. 모든 자연수 $n$에 대해 $b_{n+1} = 2a_n$ 임을 증명하여라.

2013 제74회 William Lowell Putnam 수학경시대회 B5

집합 $X=\{1,2,\ldots,n\}$와 $k\in X$가 주어져있다. 모든 $x\in X$에 대해 $f^{(j)}(x)\le k$가 되는 정수 $j\ge 0$가 존재하는 함수 $f:X\to X$의 수는 정확히 $k\cdot n^{n-1}$임을 증명하라. (여기서 $f^{(j)}$란 함수 $f$를 $j$번 합성한 것이다. 즉 $f^{(0)} (x)=x$이며 $f^{(j+1)}(x)=f(f^{(j)}(x))$이다. )

2013 국제대학생수학경시대회(IMC) 둘째날 5번문제

$2013$개의 구슬을 꿰어 만든 원형의 목걸이가 있다. 각각의 구슬은 흰색 아니면 녹색이다. 목걸이에서 임의의 연속한 $21$개의 목걸이 중에 적어도 하나의 녹색 구슬이 있으면 그 목걸이 색깔은 좋다고 하자. 가능한 좋은 색깔의 수는 홀수임을 증명하라.
(2013년 8월 9일, 불가리아, 5문제, 출처)

2013 미국 TSTST 7번문제

어떤 나라에 $n$개의 도시 $1,2,\ldots,n$가 있다고 하자. 두 도시를 잇는 고속도로를 정확히 $n-1$개를 건설해서 모든 도시가 다른 도시에서 도로를 여러개 이용해서 도달가능하게 만들고자 한다. 그런데 두 도시의 수 차이가 정확히 $1$이면 그 사이 도로를 건설하는 것은 금지되어 있으며, 도시 $1$과 도시 $n$ 사이에도 도로 건설이 금지되어 있다고 한다. 이렇게 도로를 건설하는 방법의 수를 $T_n$이라 하자.
(a) $n$이 홀수이면 $T_n$이 $n$의 배수가 됨을 증명하라.
(b) $n$이 짝수이면 $T_n$은 $n/2$의 배수가 됨을 증명하라.
(2013년 6월 25일, 4시간 반동안 3문제, 출처)

2013 국제수학올림피아드 6번문제

정수 $n$($\ge 3$)에 대하여, 원주 위에 등간격으로 놓여 있는 $n+1$개의 점을 생각하자. 이 점들에 정수 $0$, $1$, $\ldots$, $n$을 하나씩 배열한다. 한 배열을 회전시켜서 얻어지는 배열들은 모두 같은 배열로 간주한다. 어떤 배열이 다음 조건을 만족할 때, 그 배열을 ‘아름다운 원순열’이라 부르자:

(조건) $0 \le a\lt b\lt c\lt d\le n$이고 $a+d=b+c$인 임의의 네 정수 $a$, $b$, $c$, $d$에 대하여, $a$와 $d$를 잇는 현과 $b$와 $c$를 잇는 현이 만나지 않는다.

아름다운 원순열의 개수를 $M$이라 하고, $x + y \le n$과 $\gcd(x, y) = 1$을 모두 만족하는 양의 정수의 순서쌍 $(x,y)$의 개수를 $N$이라 할 때, 다음을 증명하여라:\[M = N + 1.\]
(2013년 7월 24일 콜롬비아, 출처, 4시간 30분동안 3문제)

2013 제26회 한국수학올림피아드 최종시험 6번문제

임의의 일대일대응 $f :\{1, 2, \ldots, n\}\to\{1, 2,\ldots, n\}$ ($n$은 양의 정수)에 대하여, 네 집합 $A$, $B$, $C$, $D$를 다음과 같이 정의하자. \[ A=\{i \mid i \gt f(i)\}\]\[ B=\{(i,j)\mid i\lt j \le f(j)\lt f(i)\text{ 또는 } f(j)\lt f(i) \lt i\lt j\}\]\[ C=\{(i,j)\mid i\lt j \le f(i)\lt f(j)\text{ 또는 } f(i)\lt f(j) \lt i\lt j\}\]\[ D=\{ (i,j)\mid i\lt j \text{이고 } f(i)\gt f(j)\}\] 다음 등식이 성립함을 보여라. (단, $|X|$는 집합 $X$의 원소의 개수이다.)\[ |A|+2|B|+|C|=|D|\]
(2013년 3월 24일, 4시간 30분)