Return to 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 $. 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 .$$

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 .$$

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 2^k $. My feeling is that $ S_{k,n} $ cannot be "much bigger" than $ 2^k $, regardless of $ n $. 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 .$$

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 $. 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 .$$