2000 아시아태평양수학올림피아드 5번문제

수열 $0$, $1$, $2$, $\ldots$, $n$으로 이루어진 순열 $(a_0,a_1,\ldots,a_n)$이 주어져 있다.
(순열 중에서 두 자리만 서로 바꾸는 것을 호환이라고 한다.)

$i>0$일 때 $a_i=0$이고 $a_{i-1}+1=a_j$이면 $a_i$와 $a_j$의 위치를 바꾸는 호환을 법정호환이라 하고, 순열 $(a_0,a_1,\ldots,a_n)$이 유한번의 법정호환에 의하여 순열 $(1,2,\ldots,n,0)$으로 변환할 수 있을 때 순열 $(a_0,a_1,\ldots,a_n)$을 정규순열이라고 한다. 순열 $(1,n,n-1,\ldots,3,2,0)$이 정규순열이 되는 $n$의 값을 모두 구하여라.

2001 아시아태평양수학올림피아드 1번문제

자연수 $n$에 대해 $n$을 10진법으로 쓸 때, 각 자리수의 합을 $S(n)$이라 하자. $n$을 10진법으로 나타낸 후 오른쪽부터 몇 자리수를 (최소한 한 자리 이상) 빈칸없이 잘라내어 얻은 자연수를 $n$의 ‘토막’이라 하자. $T(n)$을 $n$의 모든 토막들의 합이라 할 때, $n=S(n)+9T(n)$임을 증명하여라.

2003 아시아태평양수학올림피아드 5번문제

주어진 두 양의 정수 $m$, $n$에 대하여, 다음의 조건을 만족시키는 가장 작은 양의 정수 $k$를 구하여라.

조건: 임의의 $k$명이 모이면 그 중에는, 둘씩 서로 아는 사람끼리 $m$쌍의 커플을 만들 수 있는 $2m$명이 존재하거나, 둘씩 서로 모르는 사람끼리 $n$쌍의 커플을 만들 수 있는 $2n$명이 존재한다.

2004 아시아태평양수학올림피아드 3번문제

평면 위에, 어느 세 점도 동일 직선 위에 있지 않은 2004개의 점으로 이루어진 집합 $S$를 생각하자. 이 집합 $S$의 서로 다른 두 점을 지나는 모든 직선의 집합을 $\mathcal L$이라 하자. 다음 조건을 만족시키도록 두 가지 이하의 색 만으로 $S$의 각 점을 칠할 수 있음을 증명하시오.

조건: $S$의 임의의 두 점 $p$, $q$에 대하여 $p$와 $q$ 사이를 가르는 $\mathcal L$의 직선들의 개수가 홀수일 필요충분조건은 $p$와 $q$가 같은 색인 것이다.

여기서 직선 $\ell$이 두 점 $p$, $q$를 가른다 함은 두 점 $p$, $q$의 어느 한 점도 $\ell$ 위에 있지 않고, $\ell$에 대하여 서로 반대쪽에 있다는 뜻이다.

2005 아시아태평양수학올림피아드 4번문제

어떤 마을에 $n^2$개의 집이 $n\times n$ 바둑판 모양을 이루고 있다. 위에서 $i$번째, 왼쪽에서 $j$번째 집을 $(i,j)$라 하자. ($1\le i\le n, 1\le j\le n$) 예를 들어, $(1,1)$은 맨 윗줄 왼쪽 첫 집이다. 시간 $t=0$인 시점에 집 $(1,c)$에서 화재가 발생하였다. 단, $c\le \frac{n}{2}$. 이후 매 시간대 $[t,t+1)$ 동안, 시간 $t$인 시점에 이미 불이 붙은 집들로부터 그 집들과 이웃한 모든 집으로 불이 번지는데, 소방수들은 이 시간 동안 이웃한 집들중 한 집만을 택하여 불이 번지지 않도록 방어한다. 소방수들이 한번 방어한 집은 끝까지 불이 옮겨붙지 않으며, 진화작업은 더 이상 불이 번질 곳이 없을 때 끝난다. 소방수들은 최대 몇 집까지 화재로부터 지켜낼 수 있는가? 두 집 $(i,j)$와 $( k,\ell)$에 대하여, $\lvert i-k\rvert +\lvert j-\ell \rvert=1$일 때, 이 두 집을 서로 이웃한 집이라 한다.

2006 아시아태평양수학올림피아드 5번문제

서울 서커스 단에는 12개의 서로 다른 색 가운데 몇 개의 색을 칠하여 서로 서로를 구별하는 $n$명의 광대가 활동하고 있다. 각각의 광대는 적어도 5개의 서로 다른 색을 사용하도록 되어 있다고 한다. 어느날, 이 서커스의 단장은 어느 두 광대도 사용한 색들의 집합이 서로 같을 수 없고, 12개의 색 가운데 어느 색도 20명 이하가 사용해야 한다고 명령하였다. 단장의 명령이 가능할 수 있는 광대의 수 $n$의 최대값을 구하여라.