미친 물리학자가 어느날 실험실에서 이몬이라는 새로운 물질을 우연히 발견하게 되었따. 실험실에 있는 두 이몬끼리는 서로 엮일 수 있으며, 하나의 이몬은 여러 이몬과 엮일 수 있다. 이 물리학자는 아래와 같은 두 가지 방법의 연산을 실험실에 있는 이몬에게 적용할 수 있는 방법을 찾았다.
(i) 홀수개의 다른 이몬과 엮인 이몬은 파괴할 수 있다.
(ii) 각 이몬 $I$에 대해 그 사본 $I’$을 생성하여 전체 실험실 내 이몬을 두 배로 늘릴 수 있다. 이때 두 사본 $I’$, $J’$은 그 원본 $I$, $J$까 엮여있을때만 엮이게 되며, 각각의 사본 $I’$는 원본 $I$와 엮이게 되고, 이 외의 다른 식으로 엮인 관계가 생기거나 사라지지 않는다.
이때 이 물리학자가 이 연산들을 적절한 순서로 잘만 적용하면 서로 엮인 이몬이 없는 상태가 되도록 만들 수 있음을 보여라.
어떤 나라의 항공노선은 어떤 두 도시를 직항으로 왕복하는 노선으로 구성되어 있다. 임의의 도시에서 다른 도시로 여러 항공편을 갈아타고 갈 수 있었으며, 두 도시의 ‘거리’를 한 도시에서 다른 도시로 항공편으로 이동할 때 필요한 항공편 탑승 회수의 최솟값이라고 하자. 임의의 도시에서 정확히 거리 3 떨어진 도시의 수가 100개 이하였다고 한다. 이때 거리가 정확히 4 떨어진 도시를 2550개보다 많이 가진 도시는 존재하지 않음을 보여라.
$n$을 양의 정수라 하자. 어떤 2명의 학생도 서로 친구이거나 친구가 아니거나 둘 중의 하나인 학교에서, 다음 조건을 만족시키는 양의 정수 $a,b$의 합의 최솟값을 $N$이라 하자.
(1) 같은 팀 안의 어떤 2명도 서로 친구가 되도록, 학생들을 $a$개의 팀으로 나눌 수 있다.
(2) 같은 팀 안의 어떤 2명도 서로 친구가 아니도록, 학생들을 $b$개의 팀으로 나눌 수 있다.
학생의 수가 $n$인 학교에 대해서 $N$의 최댓값을 구하여라. 단, 학생을 팀으로 나눌 때, 어떤 학생도 정확히 한 개의 팀에 소속되도록 한다.
소수 $p$가 있다. 꼭지점이 $1000p$개인 완전그래프의 각 선에 정수값이 적혀있다면, 선에 적힌 수의 합이 $p$의 배수가 되는 (같은 꼭지점을 두 번 지나지 않는) 회로가 존재함을 증명하라.
(2013년 6월 23일, 4시간 반동안 3문제, 출처)
어떤 나라에 $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문제, 출처)
여학생 $m$명 남학생 $n$명이 있는 단체에서 임의의 두 사람은 서로를 알거나 서로를 모른다고 한다. 임의로 남학생 두 명과 여학생 두 명을 뽑아보면 그 중 어떤 남학생과 여학생은 서로 모른다고 한다. 이때 서로 아는 남학생과 여학생 쌍의 수는 $m+\frac{n(n-1)}{2}$를 넘을 수 없음을 보여라.
(2013년 8월 12일, 4시간 30분 동안 4문제, 중국 저장성, 출처)
