티스토리 뷰

문제. $n \geq 1$은 정수이고, $X$는 $n^{2} + 1$개 이상의 자연수들로 이루어진 다음을 만족하는 집합이라고 하자: 모든 $(n+1)$개의 원소를 가지는 $X$의 부분집합에는 두 개의 원소 $x \neq y$가 존재해 $x | y$이다. 이 때, 모든 $i = 1, 2, \cdots, n$에 대하여 $x_i | x_{i+1}$인 $ \left \{ x_1 , x_2 , \cdots , x_{n+1} \right \} \subseteq X$가 존재함을 보여라.


풀이.

Partially Ordered Set에 관련해 잘 알려진 내용을 적용하면 풀릴 것 같이 생겼기에, 그렇게 접근해보기로 하자.


Poset $(X, |)$를 잡자. 그러면, 조건에 의해 이것의 maximal antichain의 크기는 $n$ 이하이다. 그런데, maximal chain의 length를 $L$, maximal antichain의 width를 $W$라고 하면, $LW$가 poset 자체의 크기 이상임은 잘 알려져 있다. 이것을 이용하면 $nL \geq WL \geq n^2 + 1$이므로, $L \geq n+1$을 얻는다. 따라서, maximal chain의 크기는 $n+1$ 이상이고, 여기에서 $n+1$개의 원소를 택해서 집합을 구성하면, 문제에서 제시한 조건을 만족하는 $X$의 부분집합이 된다.


출처. Romaina TST(루마니아 국가대표 선발시험)

'수학 > 올림피아드' 카테고리의 다른 글

줄 세우기  (3) 2017.08.12
전등을 켜자!  (0) 2017.08.10
서로 나누는 집합 (Romania TST)  (0) 2017.07.29
좋은 집합 (US TST)  (0) 2017.07.29
2006 FKMO P6  (0) 2017.07.28
체스판 칠하기  (0) 2017.07.27
댓글
댓글쓰기 폼