3 ms·
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!
by stevesimmons 7y ago
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 7y agoIn 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}.