Мне всегда казалось интуитивно очевидным, что невозможно написать архиватор, который сжимает ВСЁ. Но оказалось, что это убеждение разделяют не все . И пришлось мне, некоторое время назад, быстренько доказать следующее:

Для простоты будем рассматривать сжатие последовательностей из 0 и 1. Сжатием назовем отображение последовательности на другую, так чтобы на одну последовательность не отображалось две разные (иначе нельзя однозначно разархивировать).

Суммарным коэфициентом сжатия (СКС) назовем отношение сумм длин сжатых последовательностей к сумме длин исходных.

Так вот, докажите, что, если в качестве исходного множества взять все последовательности 0 и 1 длиной меньше или равной N, то СКС >= 1.

Отсюда, в частности, следует, что если от вас требуют написать архиватор, который сжимет ВСЁ, то лучшим решением будет оставить все как есть .