# (n,k)-universal set

Set $A\subseteq\{0,1\}^n$ contains binary strings of length $n$. $A$ is $(n,k)$-universal if, for every subset $S=\{i_1,i_2,\ldots,i_k\}$ of $k$ string positions, the projection $$A|_S=\{ (a_{i_1},a_{i_2},\ldots,a_{i_k}) \mid a=(a_1,a_2,\ldots,a_n) \in A\}$$ contains all $2^k$ possible binary strings of length $k$. Show that if $\binom n k 2^k(1 - 2^{-k})^r < 1$, then there exist an $(n,k)$-universal set of size $r$.

• (1) Use proper formatting; (2) What have you tried? (Besides trying to let us do your work.) – TMM Apr 3 '13 at 19:55
• @TMM: Though it did not use MathJax and was therefore not so pretty as it might have been, the OP’s original post did use correct notation, not hard-to-read ASCII workarounds; a peremptory Use proper formatting seems unduly harsh. – Brian M. Scott Apr 3 '13 at 20:12
• @Brian: He/she has asked $9$ questions now and has not made any attempt to use LaTeX in any of them. And in the vast majority of those questions, he/she did not show any own work (and the questions are simply a verbatim copy-paste from some other source). – TMM Apr 3 '13 at 20:19
• @TMM: Those are distinct issues, and I did not comment on the second one. $\LaTeX$ is nice, but what Hai Phan did use is in fact quite readable, and I still think that your first comment is unwarrantedly harsh. – Brian M. Scott Apr 3 '13 at 20:25

Try a probabilistic interpretation: $2^{-k}$ is the probbaility of obtainig a specific bit pattern with $k$ fair coin tosses. $1-2^{-k}$ is the probability of avoiding a specific bit pattern. $(1-2^{-k})^r$ is the porbability of avoiding the same pattern $r$ times in a row. $2^k(1-2^{-k})^r$ estimates (from above) the probability of avoiding any pattern $r$ times in a row. ${n\choose k}2^k(1-2^{-k})^r$ estimates (from above) the probability of avoiding any pattern $r$ times in a row for each $k$-subset. If that probability is $<1$, "bad luck" is not guaranteed.