0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (1) Use proper formatting; (2) What have you tried? (Besides trying to let us do your work.) $\endgroup$ – TMM Apr 3 '13 at 19:55
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Apr 3 '13 at 20:12
  • $\begingroup$ @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). $\endgroup$ – TMM Apr 3 '13 at 20:19
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Apr 3 '13 at 20:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Off Topic: Does the general (n,k) universal set for non-boolean values has a name? I hardly can find anything on (n,k) universal set when every element can take more than two values. $\endgroup$ – seteropere Jan 14 '16 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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