You can make that more concise too. An ideal compressor would be able to map every string of length n to a string of length m<n and back. Since a bijection requires that its source and target sets are of the same cardinality, and there are more strings of length m than length n, this compressor cannot be a bijection. Or even more concisely: you can't fit 10 pigeons into 9 pigeonholes unless one pigeon shares.
Any programmer who does not know this near-instinctively (and also related things like the impossibility of having distinct hash values for all strings) should be ashamed of himself and brush up on basic math.
'Near-instinctive' knowledge of this, before being exposed to the basic idea, would make a good marker for high intelligence, and one which I failed at (and I'm no slouch).
Ask a few colleagues about it, and prepare to be disappointed!
I did mean "near-instinctive" to apply after having learned about the concepts of surjective, injective and bijective functions. These are so basic and important that I believe you can't be a professional programmer without having been exposed to them, and having them stick at an instinctive level.
Take the set of all files of 10 bits. There are 1024 possibilities.
You can compress these files to 9 bits. But you could also compress them to 8, 7, 6, 5, 4, 3, 2, 1, or even 0 bits. In total, that gives you: 1024 possibilities!
Of course, the issue is the initial assumption that the files all contain exactly 10 bits. If we had started with the problem of compressing files between 0 and 10 bits to files with at most 9 bits, the proof is trivial.
I knew the principle but I read the article as if set 1024 and set 512 where specific instances of the sets ence I was unable to derive the conclusion.
