[mherrmann]

What's a pigeon problem? Googling for this term only tells me what to do if I have too many pigeons flying around my house.

[FridgeSeal]

Probably referring to the Pigeonhole principle: https://en.m.wikipedia.org/wiki/Pigeonhole_principle

[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}.