# A property of Kolmogorov random strings

I am working on the following problem:

Prove that, for all $$k\in\mathbb N$$, there exists $$n\in\mathbb N$$ so that every binary string $$x\in\{0,1\}^{kn}$$ with Kolmogorov complexity $$K(x)$$ at least $$kn$$ satisfies the following property:

By interpreting $$x$$ as $$x_1\cdots x_n$$, with $$|x_i|=k$$, for any $$z\in\{0,1\}^k$$ there is an index $$i$$ for which $$x_i=z$$.

To show this, I want to suppose that if there exists a string $$x$$ of length $$kn$$ so that, after writing $$x=x_1\cdots x_n$$, not all $$k$$-bit binary strings appear in $$x_1\cdots x_n$$. Then ideally I want to show that $$x$$ can be described in less than $$kn$$ bits, which means $$x$$ have Kolmogorov complexity less than $$kn$$, which establishes the contradiction I want.

Any hints on how to do this?

For completeness, the Kolmogorov complexity of a string $$x$$ is defined as the length of the shortest description of $$x$$. And by the description of a string $$x$$, I refer to a pair $$(M,w)$$, where $$M$$ is a Turing Machine and $$w$$ is some string, so that $$M$$ halts on $$w$$ as input, leaving behind $$x$$ on the tape. I encode the pair $$(M,w)$$ as $$0^{|M|}1Mw$$. Then, for any string $$x$$, if $$M$$ is a Turing Machine that halts immediately upon execution, then $$(M,x)$$ is a description for $$x$$, of length $$2|M|+|x|+1$$. Hence the Kolmogorov complexity of $$x$$ does not exceed $$2|M|+|x|+1$$.

Suppose that $$x = x_1 \cdots x_n$$, where $$|x_i| = k$$, and there exists some $$z \in \{0,1\}^k$$ such that $$x_i \neq z$$ for all $$i$$. We can encode $$x$$ by first listing $$z$$, and then encoding each $$x_i$$ using $$\log_2 (2^k-1)$$ fractional bits. The program also needs to know $$n$$. This shows that $$K(x) \leq \log_2 (2^k-1) \cdot n + C_k + O(\log n),$$ where $$C_k$$ is a constant that depends only on $$k$$. In particular, if $$n$$ is large enough that the upper bound will be less than $$nk$$.