Let $k$ be a positive integer. Prove that a binary string (of $0$'s and $1$'s) which contains all strings of the form $SS$, where $S$ is a binary string of length $k$, has length at least $2^{k+1} + k - 1$.
Some double counting argument should work - could it be for example on the number of ''switches from 0 to 1 and 1 to 0'', i.e. the number of $2$-bit substrings $10$ and $01$ (plus some additional small terms - e.g. the $00\ldots0$ insists of additional length $k$ or $k-1$, things like that)?
Note that this bound is (probably) far from tight - even for $k=2$ the actual minimum is $12$ (relatively easy to show), so one should not be afraid of using loose countings where necessary.
Any help appreciated!