2015 제29회 한국수학올림피아드 고등부 7번문제

양의 정수 $n$이 주어져 있다. 다음 두 조건을 모두 만족하는 $m$개의 집합 $F_1$, $F_2$, $\ldots$, $F_m$이 존재하면 $m\le n$임을 보여라.
(단, 집합 $A$, $B$에 대하여 $\lvert A\rvert$는 $A$의 원소의 개수이고, $A-B$는 $A$의 원소 중 $B$의 원소가 아닌 것의 집합이다.)
(i) 모든 $1\le i\le m$에 대하여 $F_i\subseteq \{1,2,\ldots,n\}$
(ii)모든 $1\le i\lt j\le m$에 대하여 $\min(\lvert F_i-F_j\rvert, \lvert F_j-F_i\rvert)=1$

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