Maths Olympiad Prep

Library / /35 of 64

Algebra Difficulty 7.9 National olympiad, round 2 Find the answer

Let ZZ denote the set of points in Rn\mathbb{R}^n whose coordinates are 0 or 1. (Thus ZZ has 2n2^n elements, which are the vertices of a unit hypercube in Rn\mathbb{R}^n.) Given a vector subspace VV of Rn\mathbb{R}^n, let Z(V)Z(V) denote the number of members of ZZ that lie in VV. Let kk be given, 0kn0 \leq k \leq n. Find the maximum, over all vector subspaces VRnV \subseteq \mathbb{R}^n of dimension kk, of the number of points in VZV \cap Z.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The maximum is 2k2^k, achieved for instance by the subspace {(x1,,xn)Rn:x1==xnk=0}.\{(x_1, \dots, x_n) \in \mathbb{R}^n: x_1 = \cdots = x_{n-k} = 0\}.

\textbf{First solution:} More generally, we show that any affine kk-dimensional plane in Rn\mathbb{R}^n can contain at most 2k2^k points in ZZ. The proof is by induction on k+nk+n; the case k=n=0k=n=0 is clearly true.

Suppose that VV is a kk-plane in Rn\mathbb{R}^n. Denote the hyperplanes {xn=0}\{x_n = 0\} and {xn=1}\{x_n = 1\} by V0V_0 and V1V_1, respectively. If VV0V\cap V_0 and VV1V\cap V_1 are each at most (k1)(k-1)-dimensional, then VV0ZV\cap V_0\cap Z and VV1ZV\cap V_1 \cap Z each have cardinality at most 2k12^{k-1} by the induction assumption, and hence VZV\cap Z has at most 2k2^k elements. Otherwise, if VV0V\cap V_0 or VV1V\cap V_1 is kk-dimensional, then VV0V \subset V_0 or VV1V\subset V_1; now apply the induction hypothesis on VV, viewed as a subset of Rn1\mathbb{R}^{n-1} by dropping the last coordinate.

\textbf{Second solution:} Let SS be a subset of ZZ contained in a kk-dimensional subspace of VV. This is equivalent to asking that any t1,,tk+1St_1, \dots, t_{k+1} \in S satisfy a nontrivial linear dependence c1t1++ck+1tk+1=0c_1 t_1 + \cdots + c_{k+1} t_{k+1} = 0 with c1,,ck+1Rc_1, \dots, c_{k+1} \in \mathbb{R}. Since t1,,tk+1Qnt_1, \dots, t_{k+1} \in \mathbb{Q}^n, given such a dependence we can always find another one with c1,,ck+1Qc_1, \dots, c_{k+1} \in \mathbb{Q}; then by clearing denominators, we can find one with c1,,ck+1Zc_1, \dots, c_{k+1} \in \mathbb{Z} and not all having a common factor.

Let F2\mathbb{F}_2 denote the field of two elements, and let SF2n\overline{S} \subseteq \mathbb{F}_2^n be the reductions modulo 2 of the points of SS. Then any t1,,tk+1St_1, \dots, t_{k+1} \in \overline{S} satisfy a nontrivial linear dependence, because we can take the dependence from the end of the previous paragraph and reduce modulo 2. Hence S\overline{S} is contained in a kk-dimensional subspace of F2n\mathbb{F}_{2^n}, and the latter has cardinality exactly 2k2^k. Thus S\overline{S} has at most 2k2^k elements, as does SS.

Variant (suggested by David Savitt): if S\overline{S} contained k+1k+1 linearly independent elements, the (k+1)×n(k+1) \times n matrix formed by these would have a nonvanishing maximal minor. The lift of that minor back to \RR\RR would also not vanish, so SS would contain k+1k+1 linearly independent elements.

\textbf{Third solution:} (by Catalin Zara) Let VV be a kk-dimensional subspace. Form the matrix whose rows are the elements of VZV \cap Z; by construction, it has row rank at most kk. It thus also has column rank at most kk; in particular, we can choose kk coordinates such that each point of VZV \cap Z is determined by those kk of its coordinates. Since each coordinate of a point in ZZ can only take two values, VZV \cap Z can have at most 2k2^k 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.)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.