■

http://blog.pasonatech.co.jp/nextblog/sugiura/6387.html

クイズ：「どんなファイルでも、かならず元のバイト数よりも小さくなる」という圧縮方式がウソであることを説明せよ。（ヒント：マッピングの問題として考えると変換先が足りなくなりますよ...）

とりあえず考えてみた。

「どんなファイルでも、かならず元のバイト数よりも小さくなる」
この命題が真であると仮定すると、

元のファイルを圧縮しその結果を圧縮すると、「どんなファイルでも、かならず元のバイト数よりも小さくなる」
わけだから、ある時点で圧縮結果は1byteになる。

そこで、この1byteのファイルを圧縮すると、元のバイト数より小さくなるわけなので、
圧縮結果は0byteになる。

しかし、0byte、つまり存在しない情報からは、どんな情報をも復元することはできない。
つまり、1byteのファイルは圧縮できないこととなる。
「どんなファイル」は1byteのファイルも包含しているので、上記の命題は偽である。

というかんじだろうか？