2018년 제31회 한국수학올림피아드 최종시험 3번문제

지난 31년간 $n$($\ge 7$)명의 테니스 선수들이 서로 경기를 한 결과를 분석하였더니, 임의의 두 선수 $X$, $Y$를 뽑더라도 그 두 선수를 모두 이긴 적이 있는 다른 선수가 있었다는 사실을 발견하였다. 만일 어떤 정수 $k$에 대하여 $ 2(2^{(2^k)}-1)\ge n$이면 다음 조건을 만족하는 서로 다른 테니스 선수들 $A_1$, $A_2$, $\ldots$, $A_\ell$이 존재함을 보여라.

$2\le \ell\le 2k$이며 모든 $1\le i<\ell$에 대하여 $A_i$는 $A_{i+1}$을 이긴 적이 있고
$A_\ell$은 $A_1$을 이긴 적이 있다.

(단, 어떤 두 선수 $A$, $B$는 서로 경기를 한 적이 없을 수도 있고 있을 수도 있다.)

GD Star Rating
loading...
2018년 제31회 한국수학올림피아드 최종시험 3번문제, 5.0 out of 5 based on 1 rating
이 글은 조합 카테고리에 분류되었고 mo님에 의해 작성되었습니다. 고유주소 북마크.