Repeats of all binary strings of length k The question seems like it should be known, but I was not able to find it anywhere. 
How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ possible subsequences occur? 
For example, suppose $n=3$, and $k=2$. We want a set of binary strings of length $3$ so that if you look at the first and third symbols (or first two, or last two), you will see all $4$ patterns $00$, $01$, $10$, and $11$. For example, the strings with an even number of $1$s $\{ 000, 011, 110, 101\}$ induce all subsequences on each set of two positions.  
Let $f(n,k)$ be the minimum number. Trivially, $f(n,k) \ge 2^k$ so $f(3,2)=4$. 
I am interested in precise upper and lower bounds for $f(n,k)$. Bounds that are within a constant of each other (independent of $n$ and $k$) suffice for my purposes.
 A: Orthogonal arrays were mentioned in another answer, but you are not requiring that each $k$-tuple occurs exactly once in every set of $k$ columns, but rather that each $k$-tuple occurs at least once in every set of $k$ columns.
What you are looking for is called a covering array. In the usual notation for covering and orthogonal arrays, $v$ is the size of the alphabet ($2$ in this case), $k$ corresponds to your $n$, and $t$ corresponds to your $k$. Some known upper bounds for the number of rows for small values of $t,k,v$ are listed in http://www.public.asu.edu/~ccolbou/src/tabby/catable.html - you are interested in the numbers for $(t,k,2)$.
A: Definition: A $t-(v,k,\lambda)$ orthogonal array ($t \leq k$) (also called an orthogonal array of power/strength $t$) is a $λv^t × k$ array whose entries are chosen from a set $X$ with $v$ points such that in every subset of $t$ columns of the array, every $t-$tuple of points of $X$ appears in exactly $λ$ rows. I have used the standard notation for letters.
It seems to me the OP is looking for orthogonal arrays with minimal number of rows over the set $X=\{0,1\}$ with $k=n,\lambda=1,$ and $t=k$ because he wants every $k-$tuple to occur in every possible $k$ positions.
There are literally hundreds of papers and tens of constructions in this area. There are some lower bounds known for existence. I suggest he start with reading the Wikipedia entry and then moving on to tutorial papers of which there are plenty. Happy googling!
