Let $n$ be a positive integer, set $S_n = \{ (a_1,a_2,\cdots,a_{2^n}) \mid a_i=0 \ \text{or} \ 1, 1 \leq i \leq 2^n\}$. For any two elements $a=(a_1,a_2,\cdots,a_{2^n})$ and $b=(b_1,b_2,\cdots,b_{2^n})$ of $S_n$, define \[ d(a,b)= \sum_{i=1}^{2^n} |a_i - b_i| \] We call $A \subseteq S_n$ a $\textsl{Good Subset}$ if $d(a,b) \geq 2^{n-1}$ holds for any two distinct elements $a$ and $b$ of $A$. How many elements can the $\textsl{Good Subset}$ of $S_n$ at most have?
Problem
Source: China TST 2005
Tags: vector, induction, combinatorics unsolved, combinatorics
29.07.2006 17:48
I think the answer is $2^{n+1}$. See this problem. It states that the maximal number of vectors in $\mathbb R^{d}$ such that each two have non-positive scalar product is $2d$. Our problem asks for the maximal number of binary vectors of length $2^{n}$ such that each two differ in at least $2^{n-1}$ coordinates. Of course, $0$ and $1$ play no special role here. We may as well assume we’re working with vectors with entries $\pm 1$, and in this case the condition that two vectors differ in at least $2^{n-1}$ is the same thing as saying that each two vectors have non-positive scalar product. We can thus use the problem cited above for $d=2^{n}$ and conclude that $2^{n+1}$ is an upper bound for the size of a good set. In order to prove that, conversely, $2^{n+1}$ can be achieved, we look for an orthogonal basis $e_{1},\ldots,e_{2^{n}}$ of $\mathbb R^{2^{n}}$ formed with vectors having entries $\pm 1$, and take our good set to be $\{\pm e_{1},\ldots,\pm e_{2^{n}}\}$. We can construct such a basis $\{e_{i}\}$ by induction on $n$: Assuming we have the basis $e_{1},\ldots,e_{2^{n}}$ in $\mathbb R^{2^{n}}$, we can take, for example, $f_{i},\ i=\overline{1,2^{n}}$ to be the vectors of size $2^{n+1}$ formed by appending $e_{i}$ after $e_{i}$ (i.e. we just duplicate the $e_{i}$), and $f_{j},\ j=\overline{2^{n}+1,2^{n+1}}$ to be the vectors obtained by appending $e_{j-2^{n}}$ after $-e_{j-2^{n}}$. $f_{1},\ldots,f_{2^{n+1}}$ will be the basis in $\mathbb R^{2^{n+1}}$, and this completes the induction step.
31.07.2006 08:59
grobber wrote: I think the answer is $2^{n+1}$. This is the correct answer!
04.07.2022 18:44
Just linking. See this thread.