A property of Kolmogorov random strings

Question

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

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