0
$\begingroup$

Here is the question, but I even don't understand what's $k$-sample...

It seems very abstract to me somehow...

Let $S$ be a set of binary strings $a_1 \cdots a_n$ of length $n$ (where juxtaposition means concatenation). We call $S$ $k$-complete if for any indices $1 < i_1 < \cdots < i_k < n$ and any binary string $b_1 \cdots b_k$ of length $k$, there is a string $s_1 \cdots s_n$ in $S$ such that $s_{i_1}s_{i_2} \cdots s_{i_k} = b_1 b_2 \cdots b_k$. For example, for $n = 3$, the set $$S = \{001, 010, 011, 100, 101, 110\}$$ is $2$-complete since all $4$ patterns of $0$’s and $1$’s of length $2$ can be found in any $2$ positions. Show that if $$C(n, k) 2^k (1-2^{-k})^m <1,$$ then there exists a $k$-complete set of size at most $m$.

  • 0
    i don't see probability anywhere... Further, the problem could seem "very abstract", but the provided example should make it clear.2012-08-01
  • 0
    You say you don't understand "$k$-sample", but there seems to be no mention of a $k$-sample in the question?2012-08-01
  • 0
    @leonbloy: Perhaps "with probability" was a bad way of saying "using the probabilistic method" -- see my answer.2012-08-01

1 Answers 1