leejseo의 블로그

문제. $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(미국 국가대표 선발시험)