참석자가 $n$명인 연회를 생각하자. 임의의 두 참석자에 대하여, 그 둘은 친구이거나 친구가 아니다. 다음의 조건을 만족하는 두 참석자로 이루어진 쌍의 최대 개수를 구하여라:
[조건] 둘은 친구가 아니지만, 참석자 중 어느 한 명과 각각 친구이다.
태그 보관물: 그래프
2016 Baltic Way 팀수학경시대회 15번문제
발틱해에는 2016개의 항구가 있다. 두 항구 사이에는 양방향으로 여객선이 다닌다. 서로 다른 항구 $C_1$, $\ldots$, $C_{1062}$에 대해 직통편 항해를 통해 $C_1-C_2-\cdots -C_{1062}$ 순서로 다니는 것이 불가능하다고 한다. 이때 $A$의 어느 항구에서도 $B$의 어느 항구로 직통편 항해가 없는 서로 다른 477개의 항구의 집합 $A$, $B$이 존재함을 보여라.
2008 미국수학올림피아드 6번문제
수학자들이 모인 어느 학술대회에서 임의의 두 수학자 쌍을 봤더니 서로 아는 사이거나 모르는 사이였다고 한다. 점심시간이 되면 모든 참가한 수학자는 두 개의 큰 방 중 한 곳에서 식사를 한다. 각 수학자는 자기 방에 짝수명의 아는 사람이 있는 곳에서만 식사를 하고 싶어한다. 이때, 이 수학자들을 두 방으로 잘 나누는 경우의 수는 반드시 $2$의 지수승 꼴, 즉 어떤 양의 정수 $k$에 대해 $2^k$ 꼴이 됨을 증명하라.
2015 제28회 한국수학올림피아드 최종시험 3번문제
지하철역이 $3$개 이상인 도시가 있다. 이 도시에서 같은 지하철역을 두 번 이상 지나지 않고도 총 $L+1$개 이상의 지하철역을 지나는 경로가 있다면 다음 중 하나는 반드시 성립함을 보여라.(단, 지하철은 양방향으로 모두 운행한다.)
(i) 서로 다른 세 개의 지하철역 $A$, $B$, $C$가 존재하여 $C$를 지나지 않고 $A$에서 $B$로 가는 경로가 없다.
(ii) 적당한 지하철역에서 출발하여 같은 지하철역을 두 번 이상 지나지 않고 출발했던 지하철역으로 되돌아오는 방법 중 지하철역 $\lceil\sqrt{2L}\rceil $개 이상을 지나는 방법이 있다. 단, $\lceil x\rceil$는 $x$보다 작지 않은 정수 중 가장 작은 것이다.
1988 아일랜드 수학올림피아드 B3번문제
다음과 같은 버스 노선을 가진 도시가 있다:
(a) 각각의 노선마다 정확히 11개의 버스 정류소가 있다.
(b) 임의의 두 버스 정류소 사이를 노선을 갈아타지 않고 갈 수 있다.
(c) 임의의 두 버스 노선은 공통으로 지나는 정류소가 정확히 하나 있다.
이 도시에는 몇 개의 버스 노선이 있는가?
2007 아일랜드 수학올림피아드 4번문제
갑 항공사와 을 항공사는 6개 도시를 연결하는 비행 직항로를 운항하고 있다. 각각의 두 도시 쌍마다 갑과 을 중 한 회사가 (양방향의) 직항로를 운항한다. 한 회사만을 이용하여 순환여행할 수 있는 네 도시가 있음을 증명하여라. (단, 네 도시 $P$, $Q$, $R$, $S$의 순환여행이라 함은 $P \to Q \to R \to S \to P$ 와 같이 돌아오는 경로를 뜻한다.)