Student Clubs

Index the students $1,2,\ldots,1000$ . Index the clubs $1,2,\ldots,k$ . Let $A$ be the $k\times 1000$ matrix over $F_2$ (the field of two elements) so that:

• The ij-th entry is $1$ if student j is in club i.
• The ij-th entry is $0$ if student j is not in club i.

Consider the product $AA^T$ . Since each club is of odd size, the entries along the diagonal of $AA^T$ are all $1$ . Since the intersection of clubs $i,j$ $(i\neq j)$ is even, the entries not along the diagonal of $AA^T$ are all $0$ . Thus, $AA^T$ is the $k\times k$ indentity, which of course has rank $k$ . Therefore, $A$ has rank at least $k$ . But if $k>1000$ , then since $A$ is $k\times1000$ , $A$ has rank at most $1000<k$ , yielding a contradiction. Thus, $k\le 1000$ .

Moreover, as pointed out by Vishnu , it is possible for $k$ to be $1000$ . Thus, the answer is $\boxed{1000}$ .