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

어느 학교에 $2n$명의 학생이 있다. (단 $n\in \mathbb N$, $n\ge 2$.) 매주 $n$명의 학생이 여행을 간다. 몇번 여행을 간 후 살펴봤더니, 임의의 두 학생은 적어도 한 번의 여행을 함께 하였더라고 한다. 이때 이런 일이 가능한 최소의 여행수는 몇 번인가?
(2013년 8월 8일, 불가리아, 5문제, 출처)

2004 제17회 한국수학올림피아드 최종시험 3번문제

$2004$대의 컴퓨터를 케이블로 연결하여 컴퓨터 연결망을 구성하였다.
이 컴퓨터들의 집합의 부분집합 $S$에 대하여 $S$의 어떤 두 컴퓨터도 하나의 케이블로 직접 연결되지 않았을 때 $S$를 독립집합이라 하자. 임의의 독립집합의 원소의 개수가 $50$을 넘지 않도록 하고, 이때 사용된 케이블의 개수를 최소로 하였다.
(1) 컴퓨터 $L$에 장착된 케이블의 수를 $c(L)$로 나타낼 때, 두 컴퓨터 $A$와 $B$에 대하여, 그 둘이 하나의 케이블로 직접 연결되어 있으면 $c(A)= c(B)$이고, 서로 직접 연결되지 않았다면 $\lvert c(A)−c(B)\rvert \le 1$임을 보여라.
(2) 이 때 사용된 케이블의 총 개수를 구하여라.
(2004년 4월 10일, 4시간 30분, 3문제, 출처)

2003 제16회 한국수학올림피아드 최종시험 1번문제

어떤 전산실의 컴퓨터들이 다음과 같이 네트워크를 이루고 있다. 각각의 컴퓨터는 세 개의 케이블을 통하여 세 대의 다른 컴퓨터 와 직접 연결되어 있고, 임의의 두 컴퓨터는 직접 또는 (다른 컴퓨터들을 거쳐) 간접적으로 연결되어 서로 데이터를 주고 받을 수 있다. 이제 이 컴퓨터들 중 $K$대를 제거하여 서로 데이터를 주고받을 수 없는 두 대의 컴퓨터가 존재하거나 한 대의 컴퓨터만 남도록 하는 $K$의 최소값을 $k$라 하고, 한편 케이블 중 $L$개를 제거하여 서로 데이터를 주고 받을 수 없는 두 대의 컴퓨터가 존재하도록 하는 $L$의 최소값을 $\ell$이라고 하자. 이때, $k = \ell$임을 보여라.
(2003년 4월 12일, 4시간 30분, 3문제, 출처)

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

원주 위에 서로 다른 $n$개의 점이 놓여있다. 이 점들 중 임의의 한 점에서 시작하여 그 점과 그 점으로부터 시계반대방향으로
$m$번째 점을 선분으로 연결하고, 이 $m$번째 점과 이 점으로부터 시계반대방향으로 $m$번째 점을 선분으로 연결하고,… 이러한 과정을 새로운 선분이 생기지 않을 때까지 되풀이하자. 이렇게 그려진 선분들의 교점 중, 원의 내부에 있는 것들의 개수를 $I$라 할때, 다음에 답하여라. 단, $m$, $n$은 서로 소인 양의 정수로서 $6\le 2m\lt n$을 만족한다.
(a) 원주 위에 놓인 서로 다른 $n$개의 점의 위치가 변할때, $I$가 취할 수 있는 최대값을 $m$, $n$의 식으로 나타내어라.
(b) 부등식 $I≥n$이 항상 성립함을 보이고, $m=3$이고 $n$이 위의 조건을 만족시키는 임의의 짝수일 때 $I=n$인 경우가 존재함을 보여라.
(2003년 4월 13일, 4시간 30분, 3문제, 출처)