[stevesimmons]

The pigeon-hole principle.

If you have N+1 things and N pigeonholes to put them in, at least one pigeonhole must have more than 1 thing!

[tromp]

In particular, since the number of binary strings of length n exceeds the number of shorter strings, there must be a string of length n that's not described by a shorter program, i.e. that's incompressible.

More generally, the fraction of strings of length n that can be compressed by k or more bits is less than 2^{-k}.