1995 미국수학올림피아드 5번문제

어떤 모임에서, 임의의 두 사람은 서로 친하거가, 친하지 않다고 분류될 수 있다고 하자. 친한 두 사람은 서로를 `친구’라고 하고, 친하지 않은 두 사람은 서로를 `적’이라고 한다. 이 모임에 $n$명의 사람이 있고 서로 친구인 경우는 모두 $q$쌍 있다고 하자. 또, 임의의 세 명에는 항상 서로 친하지 않은 둘이 있다고 하자. 이 모임에 다음과 같은 사람이 적어도 한 명 있음을 증명하여라: 이 사람의 적들만 모아 생각했을 때 그 중에 서로 친구인 경우는 $q(1 – 4q/n^2)$쌍 이하이다.

GD Star Rating
loading...
이 글은 조합 카테고리에 분류되었고 mo님에 의해 작성되었습니다. 고유주소 북마크.