3 ms·
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 Di
by rmidthun 10y 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.
- jerf 10y agoYup, that's the one. 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.)