2 ms·
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.
by mherrmann 7y ago
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 7y agoProbably referring to the Pigeonhole principle: https://en.m.wikipedia.org/wiki/Pigeonhole_principle https://en.m.wikipedia.org/wiki/Pigeonhole_principle
- stevesimmons 7y agoThe 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}.