Ternary sequences satisfying $ x_i + y_i = 1 $ for some $ i $

Question

Consider a set of strings $ {\mathcal S} \subset \{0, 1, 2\}^n $ satisfying the following two conditions: 1.) every string in $ {\mathcal S} $ has exactly $ k $ symbols from $ \{0, 1\} $ (i.e., $ \forall x=x_1 \cdots x_n \in {\mathcal S} \;\; |\{ i : x_i = 2 \}| = n - k $), and 2.) for every two strings $ x, y \in {\mathcal S} $ there exists a location $ i \in \{1, \ldots, n\} $ such that either $ x_i = 0, y_i = 1 $, or $ x_i = 1, y_i = 0 $ (in other words, such that $ x_i + y_i = 1 $).

Denote by $ S_{k,n} $ the maximum possible cardinality of a set satisfying these two conditions. Clearly, $ S_{k,n} \geq S_{k,k} = 2^k $, for any $ n \geq k $. My feeling is that $ S_{k,n} $ cannot be "much bigger" than $ 2^k $, regardless of $ n $ (in fact, I couldn't find an example with $ S_{k,n} > 2^k $). Can one derive an upper bound that would establish this? The precise statement I am interested in proving is the following: $$ \lim_{k \to \infty} \frac{1}{k} \log_2 \max_{n \in \mathbb{N}} S_{k,n} \stackrel{?}{=} 1 .$$

Answer 1

I claim that $S_{k,n}=2^k$ for all $n\geqslant k$. Moreover, $\sum 2^{-m_i}\leqslant 1$ if the set of strings satisfies this condition, and $m_i$ denotes the number of zeros/ones in $i$-th string.

Proof. Toss a coin for each location and consider the following events enumerated by your strings: if the string has 1/0 at some location, the corresponding coin must come out heads/tails correspondingly. No two events may occur together, thus the sum of their probabilities is at most 1.