12
$\begingroup$

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

$\endgroup$

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ What 2 in some position means for the coin? $\endgroup$ Dec 6, 2020 at 19:26
  • $\begingroup$ @MaxAlekseyev nothing, the event corresponding to the string $s$ depends only on locations where $s$ has 0/1. $\endgroup$ Dec 6, 2020 at 19:27
  • $\begingroup$ Then two strings 02 and 20 may account for the same coin tossings giving two tails. $\endgroup$ Dec 6, 2020 at 19:28
  • $\begingroup$ @MaxAlekseyev but they violate the condition $\exists i: x_i+y_i=1$. $\endgroup$ Dec 6, 2020 at 19:30
  • 3
    $\begingroup$ In other words you replace the digit $2$ with the set $\{0,1\}$, and $\mathcal S$ magically becomes a family of disjoint subsets of $\{0,1\}^n$, each of cardinality $2^{n-k}$. Brilliant! $\endgroup$ Dec 6, 2020 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.