Let denote the set of points in whose coordinates are 0 or 1. (Thus has elements, which are the vertices of a unit hypercube in .) Given a vector subspace of , let denote the number of members of that lie in . Let be given, . Find the maximum, over all vector subspaces of dimension , of the number of points in .
Solution
The maximum is , achieved for instance by the subspace
\textbf{First solution:} More generally, we show that any affine -dimensional plane in can contain at most points in . The proof is by induction on ; the case is clearly true.
Suppose that is a -plane in . Denote the hyperplanes and by and , respectively. If and are each at most -dimensional, then and each have cardinality at most by the induction assumption, and hence has at most elements. Otherwise, if or is -dimensional, then or ; now apply the induction hypothesis on , viewed as a subset of by dropping the last coordinate.
\textbf{Second solution:} Let be a subset of contained in a -dimensional subspace of . This is equivalent to asking that any satisfy a nontrivial linear dependence with . Since , given such a dependence we can always find another one with ; then by clearing denominators, we can find one with and not all having a common factor.
Let denote the field of two elements, and let be the reductions modulo 2 of the points of . Then any satisfy a nontrivial linear dependence, because we can take the dependence from the end of the previous paragraph and reduce modulo 2. Hence is contained in a -dimensional subspace of , and the latter has cardinality exactly . Thus has at most elements, as does .
Variant (suggested by David Savitt): if contained linearly independent elements, the matrix formed by these would have a nonvanishing maximal minor. The lift of that minor back to would also not vanish, so would contain linearly independent elements.
\textbf{Third solution:} (by Catalin Zara) Let be a -dimensional subspace. Form the matrix whose rows are the elements of ; by construction, it has row rank at most . It thus also has column rank at most ; in particular, we can choose coordinates such that each point of is determined by those of its coordinates. Since each coordinate of a point in can only take two values, can have at most elements.
\textbf{Remark:} The proposers probably did not realize that this problem appeared online about three months before the exam, at \texttt{http://www.artofproblemsolving.com/ Forum/viewtopic.php?t=105991}. (It may very well have also appeared even earlier.)