аптека улица фонарь
Теорема: не существует архиватора, который сжимал бы без потерь все файлы длиной N бит хотя бы на один бит.
Доказательство: допустим, он существует. возьмем все 2^N возможных файлов, сожмем каждый. Каждый упакованный имеет длину не более (N-1), а разных файлов такой длины существует не более 2^(N-1). Следовательно, некоторые из исходных файлов сожмутся в одинаковую битовую последовательность, и однозначно распаковать ее будет невозможно.
Следствие: если архиватор сжимает некоторые файлы, он неизбежно уширяет другие.
Доказательство: допустим, он существует. возьмем все 2^N возможных файлов, сожмем каждый. Каждый упакованный имеет длину не более (N-1), а разных файлов такой длины существует не более 2^(N-1). Следовательно, некоторые из исходных файлов сожмутся в одинаковую битовую последовательность, и однозначно распаковать ее будет невозможно.
Следствие: если архиватор сжимает некоторые файлы, он неизбежно уширяет другие.