[atq2119]

That's really more about surjectivity and simple counting. Neither the pigeon hole principle not a max/average argument are really necessary.

Say you're trying to find a way to compress every n+1 bit string into an n bit string. Losslessness means that you have to come up with a function d from n bit string to n+1 bit string that decompresses. The number of n+1 bit string is larger, so there must be n+1 bit strings that are not in the image of d, which means that such a function d cannot exist.

[morelisp]

This is still the pigeonhole principle, just inverted - If you have more holes than pigeons (and you can’t make fractional or quantum pigeons) at least one hole must have no pigeons.

[atq2119]

It's similar, but that's not usually referred to as the pigeon hole principle.

[morelisp]

It's more than similar, it's gone from talking about the necessary properties of a function with an image smaller than its domain, to the impossibility of an inverse function as the image cannot be larger than its domain.

We might as well call this "the whole-pigeon principle."