1. 모든 동아리는 각각 짝수$\, + \, 1 = \,$홀수명의 학생이 가입해 있으며,
2. 어떤 두 동아리를 택하더라도 그 두 동아리에 모두 가입한 학생수는 언제나 홀수$\, + \, 1 = \,$짝수

이어야 한다. 따라서 이전 문제 ProbSoln #067에 의해서 $m \leq n+1$을 얻는다.

$ $

이제 $m = n+1$을 가정해 보자. $n$명의 학생을 순서대로 나열하여 각각 $s_1,\, \ldots,\, s_n$으로, $n+1$개의 동아리를 순서대로 나열하여 각각 $c_1,\, \ldots,\, c_{n+1}$으로 정의하자. 또한 각각의 $i = 1,\, \ldots,\, n+1$에 대하여, $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} 0 \qquad & \text{if} \quad i = j \\[5pt] 1 \qquad & \text{if} \quad i \neq j \end{cases} \] 과 같이 구해진다. (여기서, 그리고 앞으로의 모든 연산은 $\Z_2$에서의 연산이다.)

$ $

한 편, $\{v_{1},\, \ldots,\, v_{n+1}\}$이 선형종속(linearly dependent)이므로, 모두 $0$은 아닌 적당한 스칼라 $a_{1},\, \ldots,\, a_{n+1} \in \Z_2$이 존재하여, 다음의 벡터방정식 \[ 0 = \sum_{k=1}^{n+1} a_{k} v_{k} \] 를 만족한다. 그러면 임의의 $i = 1,\, \ldots,\, n+1$에 대하여 \[ 0 = \left( \sum_{k=1}^{n+1} 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}) = \sum_{k \neq i} a_{k} (v_{k} \cdot v_{i}) = \sum_{k \neq i} a_{k} \] 를 얻는다. 따라서 서로 다른 $i \neq j$에 대하여, \[ 0 = \sum_{k \neq i} a_{k} - \sum_{k \neq j} a_{k} = a_{j} - a_{i} \] 이므로 $a_{i} = a_{j}$가 성립한다. 여기서 $i,\,j$를 임의로 택할수 있고, 적어도 하나의 $a_{i}$는 $1$이어야 하므로, $a_{1} = a_{2} = \cdots = a_{n+1} = 1$를 얻는다. 따라서 \[ 0 = \sum_{k=1}^{n+1} a_{k} v_{k} = \sum_{k=1}^{n+1} v_{k} \tag*{$\myblue{(\ast)}$}\] 임을 알 수 있다. 또한 $\myblue{(\ast)}$로부터, \[ 0 = \left( \sum_{k=1}^{n+1} v_{k} \right) \cdot v_{i} = \underbrace{v_{i} \cdot v_{i}}_{= \, 0} + \sum_{k \neq i} \underbrace{v_{k} \cdot v_{i}}_{= \, 1} = n \] 즉, $n$은 짝수라는 결론을 얻는다.

$ $

이제 $e \in \Z_2^n$을 모든 원소가 $1$인 벡터로 정의하자. 그리고 각각의 $i = 1,\, \ldots,\, n+1$에 대하여 $v'_i = e - v_i$로 정의한다. (즉, $v'_{i}$의 $j$번째 원소는 학생 $s_j$가 동아리 $c_i$에 가입해 있는 경우에는 $0$, 그렇지 않은 경우에는 $1$이 된다.) 이제 $n$이 짝수라는 사실로부터, 임의의 $i,\, j$에 대하여, \[ \begin{align*} v'_{i} \cdot v'_{j} &= (e - v_{i}) \cdot (e -v_{j}) = \underbrace{e \cdot e}_{= \, n \, = \, 0} - \underbrace{e \cdot v_{i}}_{= \, 0} - \underbrace{e \cdot v_{j}}_{= \, 0} + v_{i} \cdot v_{j} = v_{i} \cdot v_{j} \end{align*} \] 를 얻는다. 따라서 위 논의를 다시 반복하면, \[ 0 = \sum_{k=1}^{n+1} v'_{k} \tag*{$\myblue{(\ast\ast)}$}\] 임을 알 수 있다. 하지만 $\myblue{(\ast)}$와 $\myblue{(\ast\ast)}$에 의해서, \[ 0 = \sum_{k=1}^{n+1} v_{k} + \sum_{k=1}^{n+1} v'_{k} = \sum_{k=1}^{n+1} e = (n+1)e \] 이다. 즉, $n+1 = 0$이어야 하므로 $n$이 홀수여야 한다는 결론을 얻는다. $n$이 동시에 짝수이면서 홀수일 수는 없으므로 모순이 발생하고, 이는 $m = n+1$이라는 잘못된 가정에서 출발한다. 따라서 $m \leq n+1$이면서 $m \neq n+1$이고, 최종적으로 $m \leq n$을 얻는다..