When the WinRAR trial ends

Computer Science Level 5

A string $x$ is $c$ - incompressible if

$K(x) \geq |x| - c$

for some constant $c,$ where $K(\text{}\cdot)$ stands for Kolmogorov complexity .

In the language $\Sigma^*$ where $\Sigma = \{ 0, 1 \}$ , what is the minimum possible number of strings of length $8$ that are 3-incompressible?

The answer is 225.

1 solution

Abhishek Sinha
May 27, 2015

If a string of length $8$ is $3$ -incompressible, then the length of the compressed string must be at least $8-3=5$ . Now, there are at most $1+2+2^2+2^3+2^4=31$ distinct binary strings with length at most 4, which can represen. However, there are a total of $2^8=256$ strings of length 8. Since there must be a one-to-one correspondence between a string and its compressed version (to ensure lossless decoding), by a simple counting argument, at least $256-31=225$ strings of length $8$ must be $3$ -incompresible.

When the WinRAR trial ends

The answer is 225.

1 solution

0 pending reports