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

학생 $n$명이 한 명 뒤에 다른 한 명이 서는 방식으로 원형으로 서있다. 학생들의 키가 $h_1\lt h_2\lt \cdots\lt h_n$이라고 한다. 키가 $h_k$인 학생은 키가 $h_{k-2}$이거나 작은 학생의 바로 뒤에 서 있다면 그 두 학생의 자리를 바꿀 수 있다고 한다. 이 때, $\binom{n}{3}$번 이하로 자리를 바꿔서 더 이상 자리를 바꿀 수 없는 상황이 되게 할 수 있음을 보여라.

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