|
|
|
|
|
|
by rmidthun
3385 days ago
|
|
|
Pigeonhole Principle.
The number of messages of bit length N is 2^N. You are trying to map these into 2^M compressed strings, M < N. By the Pigeonhole (or Dirichlet's Box) Principle, at least one compressed string will have more than one message mapped to it. So it cannot be reversed. |
|
|
The "literally sketchable on a post-it note" is that you can show this for 1 bit, 2 bits, and 3 bits pretty easily, and 4 bits if you sketch small enough. At that point it's not hard to see this goes to infinity, maybe not rigorously enough to pass for a proof, but pretty strong. (It's a fairly small step to an inductive proof from there, though this verges on a trivial proof by the time you've laid all the bits out.)