티스토리 뷰

수학/올림피아드

좋은 집합 (US TST)

leejseo 2017. 7. 29. 05:50

문제. $T$는 1보다 큰 자연수들로 이루어진 유한집합이다. $T$의 부분집합 $S$가 '좋은 집합'임은 다음을 만족함을 의미한다: 각각의 $t\in T$에 대하여 어떤 $s \in S$가 존재해 $gcd(s, t) > 1$이다. 이 때, $T$의 부분집합 가운데 좋은 집합의 수가 홀수임을 보여라.


풀이.

이 문제도 딱 보면 전형적인 더블카운팅을 이용해 기우성에 관한 결론을 얻어내고 싶게 생긴 문제임에 착안하자.


$T$의 부분집합 $A$에 대하여 집합 $A^{*} = \left \{ s \in T : \forall a \in A , \, gcd (a, s) = 1 \right \}$로 정의하자. 이제 우리는 다음을 만족하는 순서쌍 $(A, B)$의 개수 $P$에 대해 더블카운팅을 적용할 것이다:


(조건) $B$의 모든 원소는 $A$의 모든 원소와 서로소이다.


$B$는 정의에 의해 $B \subseteq A^{*}$이다. 따라서, $B$의 개수는 $2^{|A^{*}|}$가 되고, 이것이 의미하는 것은 $A^{*}$가 공집합인 경우에만 $P$의 기우성에 영향을 준다는 것이다. 또한, 우리는 $A$가 좋은 집합인 경우에만 $A^{*} = \emptyset$이 된다는 것을 알고 있다. 따라서, $P$는 좋은 집합의 개수의 기우성과 $P$의 기우성이 같다는 사실을 얻어낼 수 있다.


또한 $(A, B)$가 조건을 만족한다면, $(B, A)$도 조건을 만족한다는 것을 알 수 있다. 따라서, $P$의 기우성은 $(A, A)$ 꼴의 조건을 만족하는 순서쌍의 개수에만 영향을 받음을 알 수 있다. 그런데, 이런 형태의 순서쌍은 $A = \emptyset$이 유일하다. 따라서, $P$는 홀수이고, 이것은 좋은 집합의 개수가 홀수임을 의미한다.


출처. US TST(미국 국가대표 선발시험)

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

전등을 켜자!  (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
2017 IMO P1  (0) 2017.07.26
댓글
댓글쓰기 폼