양의 정수 $n$이 주어져있다. 원소가 $n$개인 집합 $X$의 모든 부분 집합의 절반보다 더 많은 집합을 원소로 가진 집합의 모음을 $\mathcal F$라 하자. 이때 $\mathcal F$에서 $\lceil \log_2 n\rceil +1$개의 집합을 잘 골라서 다음 조건을 만족하도록 할 수 있음을 보여라.
$X$의 임의의 두 서로 다른 두 원소에 대해 선택된 어떤 집합은 그 둘 중 정확히 하나만을 포함한다.
GD Star Rating
loading...
loading...