풀이. 먼저 $n \geq 15$인 경우, 위 두 조건을 동시에 만족할 수 없음을 보일 것이다. 이때 $\binom{15}{2} = 105$이므로 $A_1,\, A_2,\, \ldots,\, A_n$ 중에서 두 개의 부분집합을 고를 수 있는 경우의 수는 최소 $105$가지이다. 만약 첫번째 조건을 만족한다면 임의의 서로 다른 $i,\, j \in [n]$에 대하여 $a_{i,j} \in S \setminus (A_i \cup A_j)$를 택할 수 있다. 그러면 비둘기집의 원리_{(pigeonhole principle)}에 의해 적당한 $i,\,j,\,k,\,l \in [n]$이 존재하여 $a_{i,j} = a_{k,l}$이 성립한다. (단, $i \neq j$, $k \neq l$, $\{i,\, j\} \neq \{k,\, l\}$.) 이때 $i,\, j,\, k,\, l$ 중 적어도 세 개는 다른 수이므로, 일반성을 잃지 않고 $i,\, j,\, k$가 서로 다르다고 가정하면 $a_{i, j} \; (= a_{k, l}) \notin A_i \cup A_j \cup A_k$가 되어 두번째 조건을 만족하지 못한다.

$ $

이제 $n = 14$일 때 위 두조건을 동시에 만족하는 $A_1,\, A_2,\, \ldots,\, A_n$가 존재함을 보이자. 우선 $\binom{14}{2} = 91$이므로 두 개의 부분집합을 선택하는 경우의 수는 $91$가지이다. 따라서 이 각각의 경우와 집합 $T = \{1,\, 2,\, \ldots,\, 91\}$를 일대일 대응 시킬 수 있다. 이러한 일대일 대응 관계를 $m_{i,j} \in T \leftrightarrow \{A_i,\, A_j\}$로 나타내자. 그리고 각각의 $i \in [n]$에 대하여 \[ A_i = S \setminus \Big( \bigcup_{j \neq i} \{m_{i, j}\} \Big) \] 로 정의하자. 그러면 어떤 두 개의 부분집합 $A_i,\, A_j$를 택하더라도 $A_i$와 $A_j$가 공통으로 가지지 않는 원소는 $m_{i, j}$ 하나뿐이므로 $A_i \cup A_j = S \setminus \{m_{i, j}\}$가 되어 첫번째 조건을 만족한다. 또한 세 개의 서로 다른 부분집합 $A_i,\, A_j,\, A_k$를 택하면, $m_{i, j} \in A_k$이므로, \[ A_i \cup A_j \cup A_k = (S \setminus \{m_{i, j}\}) \cup A_k = S \] 가 되어 두번째 조건 또한 만족함을 알 수 있다.$ $