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
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.
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.
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.
The proposers probably did not realize that this problem appeared online about three months before the exam, at Forum/viewtopic.php?t=105991}. (It may very well have also appeared even earlier.)