풀이. $n$명의 학생을 순서대로 나열하여 각각 $s_1,\, \ldots,\, s_n$으로, $m$개의 동아리를 순서대로 나열하여 각각 $c_1,\, \ldots,\, c_m$으로 정의하자. 또한 각각의 $i = 1,\, \ldots,\, m$에 대하여, $n$차원 벡터 $v_{i}$의 $j$번째 원소를 학생 $s_j$가 동아리 $c_i$에 가입해 있는 경우에는 $1$, 그렇지 않은 경우에는 $0$으로 정의하자. 여기서 각각의 벡터 $v_i$의 모든 원소는 $0$ 또는 $1$이므로 체 $\Z_2$위에서 정의된 $n$차원 벡터공간 $\Z_2^n$의 원소로 이해할 수 있다. 한 편, 문제의 조건 (1)과 (2)에 의해서 $v_{i}$와 $v_{j}$의 내적은 \[ v_{i} \cdot v_{j} \equiv \begin{cases} 1 \qquad & \text{if} \quad i = j \\[5pt] 0 \qquad & \text{if} \quad i \neq j \end{cases} \] 과 같이 구해진다. (여기서, 그리고 앞으로의 모든 연산은 $\Z_2$에서의 연산이다.)

$ $

이제 $\{v_{1},\, \ldots,\, v_{m}\}$이 선형독립(linearly independent)임을 보이자. 이를 위해 적당한 스칼라 $a_{1},\, \ldots,\, a_{m} \in \Z_2$이 존재하여, 다음의 벡터방정식 \[ 0 = \sum_{k=1}^{m} a_{k} v_{k} \] 를 만족한다고 하자. 그러면 임의의 $i = 1,\, \ldots,\, m$에 대하여 \[ 0 = \left( \sum_{k=1}^{m} a_{k} v_{k} \right) \cdot v_{i} = a_{i} (v_{i} \cdot v_{i}) + \sum_{k \neq i} a_{k} (v_{k} \cdot v_{i}) = a_{i} (v_{i} \cdot v_{i}) = a_{i} \] 가 되어 모든 $i = 1,\, \ldots,\, m$에 대하여, $a_{i} = 0$을 얻는다. 즉, $\{v_{1},\, \ldots,\, v_{m}\}$은 선형독립이고, 따라서 $m \leq n$이어야 한다..