2017 일본수학올림피아드 본선 4번문제

$n$은 3 이상의 정수로 주어져 있다. $n$명의 사람이 있어, 그 중 3명 이상이 참가하는 집회가 매일 열린다고 한다. 각각의 집회에 대해, 참가한 사람들 모두가 서로와 정확히 한 번 악수를 한다고 한다. $n$일째의 집회가 끝나고 난 후, 어떤 두 명을 뽑아도 모든 집회에 걸쳐 정확히 한 번 악수를 했다고 한다. 이 때, 집회에 참가한 사람 수는 항상 일정함을 보여라.

2016 일본수학올림피아드 본선 5번문제

$m,n$은 양의 정수로 $m \geq 2, n<\frac{3}{2}(m-1)$이 성립한다고 한다. 어느 나라에 $m$개의 도시와 $n$개의 도로가 있어, 각각의 도로는 2개의 서로 다른 도시를 연결하고 있다. 두 도시를 연결하는 도로는 두 개 이상 있을 수도 있다. 이제, 도시를 2개의 그룸 $\alpha,\beta$로 분류해서, 그룹 $\alpha$의 도시와 그룹 $\beta$의 도시를 연결하는 도로를 전부 고속도로로 만들기로 한다. 이 때, 다음 조건을 만족하는 분류법이 존재함을 보여라: - 두 그룹은 각각 도시를 1개 이상 포함한다. - 모든 도시에 대해서 그 도시와 연결된 고속도로는 1개 이하이다.

1981 미국수학올림피아드 2번문제

어느 나라의 임의의 두 도시는 버스, 열차, 비행기 중 꼭 하나의 탈 것으로 연결되어 있다. 세 가지 탈 것은 이 나라에서 모두 쓰여지고 있고, 세 가지 탈 것이 한 도시에서 모두 운행되는 경우는 없으며, 또 어떤 세 도시를 택해도 그들이 모두 같은 탈 것으로 연결되지는 않는다고 한다. 도시는 최대 몇 곳이나 있는가?

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

어떤 섬에 $n$개의 성이 있고, 각 성은 $A$, $B$ 나라 중 하나에 속한다고 하자. 각 성에는 그 나라의 장수가 1명씩 있다. 어느 두 성 사이에 다른 성을 지나지 않고 이동할 수 있는 길이 있으면 그 두 성이 이웃한다고 하자. 다음 두 명제가 필요충분조건임을 보여라.

(조건 1) $B$나라의 장수들 중 일부가 각각 이웃한 $A$성 중 하나를 무작위로 골라 동시에 공격하더라도, $A$나라 장수들 중 일부를 이웃한 성들으로 동시에 잘 움직여 방어를 하게 하면, $A$나라 각 성에 대하여, 그 성으로 공격하는 $B$나라 장수의 수보다 그 성을 방어하는 $A$나라 장수의 수가 크거나 같게 할 수 있다.

(조건 2) $A$나라 성들로 이루어진 임의의 집합 $X$에 대해, $X$에 속하거나 $X$ 중 적어도 하나에 이웃한 $A$나라 성의 개수가, $X$중 적어도 하나에 이웃한 $B$나라 성의 개수보다 많거나 같다.