An incompressible string is a string with Kolmogorov complexity equal to its length, so that it has no shorter encodings. The pigeonhole principle can be used to be prove that for any lossless compression algorithm, there must exist many incompressible strings.